Common combinators in JavaScript

combinators.js

const I  = x => x
const K  = x => y => x
const A  = f => x => f (x)
const T  = x => f => f (x)
const W  = f => x => f (x) (x)
const C  = f => y => x => f (x) (y)
const B  = f => g => x => f (g (x))
const S  = f => g => x => f (x) (g (x))
const S_ = f => g => x => f (g (x)) (x)
const S2 = f => g => h => x => f (g (x)) (h (x))
const P  = f => g => x => y => f (g (x)) (g (y))
const Y  = f => (g => g (g)) (g => f (x => g (g) (x)))

combinators.md

Name	#	Haskell	Ramda	Sanctuary	Signature
identity	I	id	identity	I	a → a
constant	K	const	always	K	a → b → a
apply	A	($)	call	I¹	(a → b) → a → b
thrush	T	(&)	applyTo	T	a → (a → b) → b
duplication	W	join²	unnest²	join²	(a → a → b) → a → b
flip	C	flip	flip	flip	(a → b → c) → b → a → c
compose	B	(.), fmap²	map²	compose, map²	(b → c) → (a → b) → a → c
substitution	S	(<*>)²	ap²	ap²	(a → b → c) → (a → b) → a → c
chain	S_³	(=<<)²	chain²	chain²	(a → b → c) → (b → a) → b → c
converge	S2³	apply2way, liftA2², liftM2²		lift2²	(b → c → d) → (a → b) → (a → c) → a → d
psi	P	on	on	on	(b → b → c) → (a → b) → a → a → c
fix-point⁴	Y	fix			(a → a) → a

---

¹) The A-combinator can be implemented as an alias of the I-combinator. Its implementation in Haskell exists because the infix nature gives it some utility. Its implementation in Ramda exists because it is overloaded with additional functionality.

²) Algebras like ap have different implementations for different types. They work like Function combinators only for Function inputs.

³) I could not find a consistent name for these combinators, but they are common enough in the JavaScript ecosystem to justify their inclusion. I named them myself in order to refer to their implementation.

⁴) In JavaScript and other non-lazy languages, it is impossible to implement the Y-combinator. Instead a variant known as the applicative or strict fix-point combinator is implemented. This variant is sometimes rererred to as the Z-combinator. The implementation found in combinators.js is the strictly evaluated "Z" combinator, which needs the extra wrapper around g (g) on the right hand side.

references.md

Note that when I use the word "combinator" in this context, it implies "function combinator in the untyped lambda calculus".

• To Mock a Mocking Bird (book of combinatory puzzles and examples)
• Combinator Birds (summary of all combinators named by the book)
• CombinatorsJS (implementation of all the same combinators in JavaScripts)
• Fantasy Combinators (implementation of common combinators in JavaScript)
• Collected Lambdas (collection of noteworthy combinators)
• Programming With Nothing (talk)
• Church Encoding (wikipedia)
• Fixed-point combinator (wikipedia)
• Lambda calculus (wikipedia)
• SKI combinator calculus (wikipedia)
• BCKW combinator calculus (wikipedia)

@glebec don't be dissatisfied - you have given me plenty to work through and its great fun!
So far I have only worked with the Bool adt. I'm posting it here, so you can comment if I have misunderstood. I plan to go through the other types later.

//                case arguments
//            /-------------------\
const True  = trueCase => falseCase => trueCase
const False = trueCase => falseCase => falseCase
//            \________________________________/
//                     boolean encoding
// Scott encoding:
// Bool  = True | False
// True  = \x _ -> x
// False = \_ y -> y
var darkMode = False
var backgroundColor = darkMode ("black") ("white") // using the `darkMode` bool
console.debug (darkMode,        // <- Function: False
               backgroundColor) // <- white

var darkMode = True
var backgroundColor = darkMode ("black") ("white") // using the `darkMode` bool
console.debug (darkMode,        // <- Function: True
               backgroundColor) // <- black

// wrapped values (constructor args)
//           /----\
const Pair = x => y => access => access(x) (y)
//                     \_____________________/
//                          pair encoding
//           \-------------------------------/
//                     constructor
// Scott encoding:
// Pair x y = Fst | Snd
// Fst      = \x _ -> x
// Snd      = \_ y -> y
const numPair = Pair (5)    (9)
const strPair = Pair ("hi") ("bye")
var   fst     = x => _ => x
var   snd     = _ => y => y
console.debug (numPair (snd), // <- 9
               strPair (snd)) // <- bye

// Pair can also be derived from Bool
// Scott encoding:
// Pair x y    = Bool = True | False
// True  = Fst = \x _ -> x
// False = Snd = \_ y -> y
var fst        = True
var snd        = False
console.debug (numPair (snd), // <- 9
               strPair (snd)) // <- bye

@glebec I can see that my Scott encoding of Pair is wrong. But what should it be?

Pair x y = x y (\x _ -> x) | x y (\_ y -> y)?

Pair x y = \ fn . fn x y

functionally equivalent to Pair x y fn = fn x y, but trying to express that a pair is a ( binary ) function that accepts a ( binary ) function and applies that function to the values contained in the closure / pair.

The Scott encoding is Pair x y = Pair x y, which seems unhelpful. But note that there is only one, binary, constructor, which is entirely different from Boolean, where there are two nullary constructors.