# Do Applicative Functors generalize the S & K Combinators?

If the title hasn’t scared you off yet, here’s the story: I was hacking on
someone else’s code on
the plane and trying to wrap my head around some
`Applicative`

class
code; in particular the code in
question used the Applicative instance for `((->) a)`

i.e. functions. This
turned my brain to cream-of-wheat and I had to take a break.

If you aren’t familiar with **Applicative Functors**, they are somewhere in
between the familiar and simple `Functor`

class and the `Monad`

class; an
abstraction for function application with a context. Check out
here for more. Away
from the computer I got out a pad of paper and went about trying to figure out
how the `<*>`

method was defined over functions. Here are the types:

*The polymorphic type:*

```
(<*>) :: (Applicative f) => f (a -> b) -> f a -> f b
```

*Substitute (x -> ...) for f to get the type for the functions instance:*

```
(<*>) :: (x -> a -> b) -> (x -> a) -> (x -> b)
```

You can try defining the instance from the type definition; there seems to be
only one sensical way. When I did it I was struck by something: the definition
for the function above *is the same as the S combinator in the SKI combinator
calculus!*

At that point I started looking for other connections to combinatory logic,
and quickly noticed that *the class method pure was essentially the K
combinator!*. Here is the actual instance definition:

```
instance Applicative ((->) a) where
pure = const
(< *>) f g x = f x (g x)
```

For those not familiar, the **SK(I) Combinator Calculus** is a formal system
for modelling computation, much like the lambda calculus; one can express any
computable function using only the three (actually only S and K are necessary)
symbols and parentheses. I’ve written about and
implemented the combinator calculus,
and you can read more on the
wikipedia page.

### Exploring the Connection

It’s pretty astounding to me that the only two methods required to define an
Applicative instance turn out to be sufficient (the details of haskell’s type
system aside) to define a complete combinator base, *capable of expressing any
computable function.*

At first I wondered whether this connection was the brainchild of some clever
haskeller who defined the (->) instance, and therefore somewhat artificial.
But it turns out that the definitions for `pure`

and `(< *>)`

fall out quit
naturally from the type definitions. So naturally in fact that we can use
djinn to automatically derive
their definitions!:

```
Djinn> ? (<*>) :: (x -> a -> b) -> (x -> a) -> (x -> b)
(<*>) :: (x -> a -> b) -> (x -> a) -> x -> b
(<*>) a b c = a c (b c)
Djinn> ? pure :: a -> (x -> a)
pure :: a -> x -> a
pure a _ = a
```

Observe how the function definitions above could have been pulled right from an explanation of the S and K combinators.

Now let’s play with this in GHCi. We’ll first define our S and K combinators as the Applicative methods (giving type hints to keep the typechecker happy), then define the I combinator in terms of S and K, then we’ll express a Church numeral:

```
Prelude> :m + Control.Applicative
Prelude Control.Applicative> let s = (<*>) :: (x -> b -> c) -> (x -> b) -> (x -> c)
Prelude Control.Applicative> let k = pure :: a -> (x -> a)
Prelude Control.Applicative> let i = s k k
Prelude Control.Applicative> let two = s (s (k s) k) i
Prelude Control.Applicative> two ('x':) []
"xx"
```

In the last last line above we sort of “render” the church numeral by applying
it to a function and value that will construct a list; remember that church
numerals represent integers as *n-fold function composition*; in the lambda
calculus the numerical represenatations are more straightforward: `two = \f x-> f (f x)`

, but the idea is the same.

### Conclusion

It makes a lot of sense that a general type class meant to aid programming in
an “applicative” style would have some similarity with the combinator calculus
(in which *even data* is function application), but I thought it was pretty
exciting to see such a fundamental computer science concept seemingly emerge
naturally out of a library designed to solve a very high-level problem.

I have no idea whether these observations are novel or old and obvious, but would love to hear from anyone who has any thoughts on this.

**EDIT:** After taking a closer look at
Conor McBride and Ross Paterson’s paper
on Applicative Functor’s, I see now that he labels his ((->) a) instance
methods with “S” and “K”, but does not explore the subject further. So I’m
leaning towards obvious. Thanks for reading :)