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)

@dotnetCarpenter I'll attempt to make it as clear yet short as I can.

Scott encodings are a way to represent arbitrary data types that are made up of different cases (e.g. case True vs case False, or case EmptyList vs case List of head and tail) each of which may contain some sub-data (e.g. List of head and tail).

Booleans

The Scott encoding for booleans is the same as the Church encoding: namely, a bool is a function that takes two arguments (what to do if the bool is True and what to do if the bool is False):

//          case arguments
//      /-------------------\
True  = trueCase => falseCase => trueCase
False = trueCase => falseCase => falseCase
//      \________________________________/
//              boolean encoding

We have two values in our datatype (True and False) so we have two functions (one represents each value); and each of those functions is used by supplying two arguments (what to do in each case). We could then use it like this:

// one of the following is active, but we don't know which:
// darkMode = True
// darkMode = False

backgroundColor = darkMode("black")("white") // using the `darkMode` bool

We take our boolean variable darkMode and we feed it what to do in each case (the case where darkMode is True and the case where darkMode is False). If the former, our result is "black", and if the latter, our result is "white".

Types with 3 values

Booleans have two values. What if we have a datatype with three values – say, Rock | Paper | Scissors?

//                    case arguments
//         /----------------------------------\
Rock     = rockCase => paperCase => scissorCase => rockCase
Paper    = rockCase => paperCase => scissorCase => paperCase
Scissors = rockCase => paperCase => scissorCase => scissorCase
//         \_________________________________________________/
//                        RPS encoding

There are three functions (one for each value), and each takes three arguments (what to do in each case) and uses just one of them (e.g. the Paper function returns what the user wants to do if the value is Paper – since the Paper function "knows" it is indeed Paper).

We could use it like this:

action = gameSign("slam")("wrap")("cut")

Socratic question for you: if gameSign is the function Scissors, what will action be set to?

Pairs / 2-tuples

The above shows how to write Scott encodings for types with multiple different cases (the value is Rock or Paper or Scissors). But Scott encodings also handle when a type contains multiple values at once (the value contains a Bool and a GameSign). One such example type is Pair, aka a 2-tuple.

//  wrapped vals (constructor args)
//     /----\
Pair = x => y => access => access(x)(y)
//               \____________________/
//                    pair encoding
//    \------------------------------/
//          constructor

Here, Pair is a constructor which takes two arguments (the values to wrap / contain) and returns the resulting encoding of the pair (the function access => access(x)(y). We could use the constructor Pair to make some pairs like this:

numPair = Pair(5)(9)
strPair = Pair("hi")("bye")

And elsewhere we could use the encoded pairs by supplying a function which will be fed access to each of the wrapped values:

firstNum = numPair(x => y => x) // 5
firstStr = strPair(x => y => x) // "hi"

Socratic question for you: how would you grab the second value of each pair?

Types with both cases and wrapped values

We've seen examples of Scott encodings for one of several possibilities (Bool, RPS) and an example of a Scott constructor / encoding for a value that contains multiple values. What if we have a type that combines both of these features? A value might be A or B, and if it's B, it contains sub-value X.

An example of such a type is Maybe, aka Option or Optional in some languages:

//                      encoding for Nothing | Some
//             /------------------------------------------\
Nothing =      handleNothing => handleSome => handleNothing
Some    = x => handleNothing => handleSome => handleSome(x)
//       \________________________________________________/
//                    constructor for Some

We have two cases (either a value is Nothing or Some x) so we have two functions, and the encoding takes two arguments (what to do if the value is Nothing / what to do if it's Some). But the Some encoding has to be constructed by feeding a value to wrap over (x). And to access that value, we need to feed a function as an argument, which Some will pass x into so the user can use it.

Example use case:

// loggedInUser is one of these:
// loggedInUser = Nothing
// loggedInUser = Some("Naomi")

message = loggedInUser("Nobody is logged in")(name => `Welcome, ${name}!`)

If loggedInUser is Nothing, then we use a default value; but if it's Some("Naomi"), we feed a function to get access to the wrapped name, which we can then use.

Recursive Types

Now we finally come to the example of a singly-linked list. Our list encoding will be like Maybe above in that it has two cases: the empty list, or a list cell with a value (the "head") AND with a continuation of the list (the "tail"). Since we have two cases, we'll have two functions. Since the full list wraps two values, our constructor will take two arguments.

//                               encoding for Empty | Cell
//                      /-------------------------------------------------\
Empty =                 handleEmpty => handleCell => handleEmpty
Cell  = head => tail => handleEmpty => handleCell => handleCell(head)(tail)
//      \_________________________________________________________________/
//                     constructor for Cell

We can use the Cell construcror like this:

shoppingList = Cell("potato")(Cell("milk")(Cell("chicken")(Empty)))

And then elsewhere, you could consume the shoppingList encoding like this:

secondItem =
  shoppingList("There is no item1")(item1 => more => more("There is no item2")(item 2 => more => item2))

Challenge question: can you figure out how to use the Y-combinator to get the length of shoppingList?

Conclusion

I just finished writing this and truth be told I am dissatisfied with it. It's much longer and less clear than I hoped. But I'm posting it because I can't spend more time right this second trying to make it better, and maybe despite those deficiencies, it will still help you make progress in your understanding. I hope so at any rate!

@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.