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)

Shouldn't the signature for fix-point be (f -> a -> a) -> a? -- @dotnetCarpenter

I'm going to assume you meant (f -> a -> a) -> a -> a. You missed an extra a -> ... for input you're giving in YFact (4). Under that assumption, you are almost correct!

There's a little thing missing though. You specified f in that signature, but what is f? You're implying it's a function by using the letter f, but you haven't given that function a signature. What is the signature of f? In your factorial example it's the fact function, so let's go with that. You called fact on n - 1 (which is a member of a) and it produced another a (we know that, because you're multiplying its result). So the signature of f is actually a -> a! Let's update our whole signature:

Y :: ((a -> a) -> a -> a) -> a -> a
--     \    /                \  /
--      \  /                  and this is the function input you forgot originally
--       that's the expansion of `f`

Interestingly, we see a pattern arise: (a -> a) occurs three times! We can see that more clearly if I add the implicit braces explicitly. I'll also give the three functions some names so we can talk about them.

Y :: ((a -> a) -> (a -> a)) -> (a -> a)
--     \    /      \    /       \    /
--      recur      output        fixed

I'll add names to your example as well, to make it easier to talk about:

const fixed = Y (recur => function output(n){ return n === 0 ? 1 : n * recur (n - 1) });

The recur function is what you call to trigger the recursion. But recursion into what? Well, into the output function. And then the fixed function is what's returned from the whole thing.

Now why did recur and fixed have the shape a -> a? It's because output has that shape! The recur function just calls back into output, so it has the same shape as output. And fixed has the same shape as output too, because Y is just returning your output.

You already discovered that you can change the shape of output with your definition of YPlus, and that recur and fixed just followed:

const fixed = Y (recur => function output(n){ return m => n === 0 ? m : 1 + recur (n - 1) (m) })

That's your second example, updated to include the names. You updated output to take two arguments, and consequently recur and fixed also took two arguments. The Y function now has the following signature:

Y :: ((a -> a -> a) -> (a -> a -> a)) -> (a -> a -> a)
--     \         /      \         /       \         /
--        recur            output            fixed

Where did that third -> a come from?! From your own output function! Can we also reduce the number of -> as by not returning a function at all?

Y (recur => ({output: 42}))
// -> {output: 42}

Yep! 😄 In this last example, the signature of Y is:

Y :: (a -> a) -> a

And that signature actually works for all the other examples too, because a -> a, a -> a -> a, or any other Function or value are all members of a, so long as they are consistent throughout the type signature. So the least restrictive signature for the Y function is (a -> a) -> a 🎉

The signature (a -> a) -> a basically captures the pattern we saw, that whatever a you're returning from a -> a (even if it's a function) is the same a that you get as input, and the same a that is returned as final output.

Thanks @Avaq for, as usual, a beautiful example!

I guess Scott encoding, is the succinct way to describe your detailed examples. But I think your explanation is more beautiful non the less.

Big thanks to @glebec for explaining how a linked list implementation correspond to Scott encoding of the same list.

You both have mad ascii skillz

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