If someone mentions “combinators”, you may first think about the Y-Combinator, most likely because of a certain startup incubator and the orange website associated with it. The Y combinator is neat, and honestly is the first thing that got me interested in combinators in general. But it’s also fairly impenetrable at a first glance, and even after staring at it for awhile, it’s not obvious why it works. Early on when I was trying to figure it out, I went through the exercise of applying Y to some simple application (probably factorial), and I manually walked through interpreting each step on paper to try to follow how it worked. If I remember correctly, I did see that it worked, but I’m not going to say that I wholly grasped why it was working.
The core combinators are S, K, and I. All the other combinators can be composed from these three. Haskell Curry showed that I can also be formed from S and K (SKK is equivalent to I), so actually just the 2 are the essential combinators. SKI combinators are actually equivalent to lambda calculus in what they can express, which in turn is Turing-complete… Now, you wouldn’t want to program something complex in strings of just S & K, but it’s pretty cool that you could. I’ve read that the original Miranda implementation (Miranda was one of the precursors to Haskell) worked by compiling down to SKI combinators, which is pretty cool.
I is about as simple as you could imagine:
I = ->(x){ x }
I is the identity function. It just gives you back whatever you give it. At first glance, this doesn’t seem very useful, but once you start using other combinators together, you find that sometimes exactly what you want is to just have a function that returns whatever it was given. I’ll try to get to an example of this before this is done.
K is similarly pretty simple:
K = ->(x){ ->(y) { x } }
K is sometimes called the “constant” function; it accepts two arguments, and returns the first one. Or, if you have curried the function, like I did above, it becomes a function that just returns whatever argument it was first applied to, regardless of whatever you give it next. For example:
always_2 = K.(2)
always_2.(3)
=> 2
always_2.(42)
=> 2
always_2.("hello")
=> 2
So, that is K. Similar to I, you might look at this and wonder what it’s good for. In what scenario would we use this? Let’s leave that again for a bit.
Now here’s S:
S = ->(x){ ->(y){ ->(z) { x.(z).(y.(z)) } } }
S takes three arguments, which need to be a binary function, a unary function, and a value.
In practice, it works like this:
add = ->(x){ ->(y) { x + y } }
double = ->(x){ x * 2 }
add_to_double = S.(add).(double)
add_to_double.(4)
=> 12
Okay, let’s try to show how combinators can actually do something a little more interesting. To do that, we need a couple other combinators: B and Phi.
B is also called the composition combinator: it just composes two functions:
B = S.(K.(S)).(K)
Or, in a more lambda-calculus style so we can see how what it does a little easier:
B = ->(x){ ->(y){ ->(z) { x.(y.(z)) } } }
In even simpler mathematical terms, if you have a function f and a function g, and you compose them (sometimes the . is used as the composition operator) then:
(f . g) x = f(g(x))
That’s it: that’s all there is to composition. Not quite the same as S, this would work like this:
add_one = ->(x){ x + 1 }
double = ->(x){ x * 2 }
double_and_add_one = B.(add_one).(double)
double_and_add_one.(5)
=> 11
The Phi combinator is:
# in terms of other combinators:
Phi = B.(B.(S)).(B)
# in lamdba-like terms:
Phi = ->(x){ ->(y){ ->(z) { ->(n) { x.(y.(n)).(z.(n)) } } } }
Phi needs 4 arguments: three functions (a binary function and two unary functions), and some value or object. The object will be passed to each of the two unary functions, and each of those results will be passed to the binary function. Phi can express some useful things really elegantly; for example, the average function.
Normally, we might write average something like this:
average = ->(list) { list.sum / list.length.to_f }
Looking at this, we have three functions: sum and length (for the incoming list), and division (on the values of the sum and length from the list). This is exactly the same sort of functions that Phi needs. What if we passed them to Phi?
divide = ->(x){ ->(y) { x / y.to_f } }
length = ->(l){ l.length }
sum = ->(l){ l.sum }
average = Phi.(divide).(sum).(length)
average.([1,2,3])
=> 2.0
Or we could implement a palindrome checker:
equals = ->(x){ ->(y){ x == y } }
reverse = ->(s){ s.reverse }
palindrome = Phi.(equals).(I).(reverse)
palindrome.("madam")
=> true
palindrome.("hello")
=> false
palindrome.("racecar")
=> true
In our palindrome checker, we need to check if the reversed string is equal to the original string; so, as promised, we used the I combinator for this. Phi needs a function there, and I gives us back the original string so that we can compare it to the reversed version.
How about one of the Leetcode problems? Here’s leetcode #217: “Contains Duplicate”
“Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.”
not_equals = ->(a){ ->(b){ a != b } }
length = ->(l){ l.length }
unique_length = ->(l){ l.uniq.length }
contains_duplicate = Phi.(not_equals).(length).(unique_length)
contains_duplicate.([1,2,3,3,4])
=> true
contains_duplicate.([1,2,3,4,5])
=> false
Here’s one more. What if we had a version of Phi where we pass our fourth argument unchanged to all three of the first arguments?
Phi is sometimes called “fork”, because if you draw it out, it resembles a fork shape:
[1,2,3]
↓ ↓
sum length
↘ ↙
↓
div
↓
output
Say we wanted to solve FizzBuzz. We could have a fizz function, that returns “Fizz” if n%3 == 0, and empty string otherwise. And we could have a similar function for “Buzz”. But in the last step, when we need to combine them, we’d also need n … if we have an empty string, we’d know we should just return n, but we don’t have n anymore. We could have our fizz and buzz functions pass it along, but then our combine function at the end gets kind of complicated and ugly. Instead, what if we also pass n to the first function?
fork3 = ->(x){ ->(y){ ->(z){ ->(n){ x.(n).(y.(n)).(z.(n)) } } } }
This is just like Phi, but the first function, x, also gets a reference to n
n
↓ ↓ ↓
fizz ↓ buzz
↘ ↓ ↙
↓
combine
↓
out
So, now we could do:
fizz = ->(n){ n % 3 == 0 ? "Fizz" : "" }
buzz = ->(n){ n % 5 == 0 ? "Buzz" : "" }
combine = -->(n){ ->(fizz){ ->(buzz){
fb = fizz + buzz
fb.empty? ? n : fb
}}}
fizzbuzz = fork3.(combine).(fizz).(buzz)
[1,2,"Fizz",4,"Buzz","Fizz",7,8,"Fizz","Buzz",11,"Fizz",13,14,"FizzBuzz"] == (1..15).map(&fizzbuzz)
=> true
So… these are SKI combinators! Or at least, some of them. And there’s also the Y combinator, but that’s a different post, I think. Or you can just watch Jim Weirich talk about that.