S combinator in Haskell

Question

Can an analog of the S combinator be expressed in Haskell using only standard functions (without defining it by equation) and without using lambda (anonymous function)? I expect it to by of type (a -> b -> c) -> (a -> b) -> a -> c.

For example, an analog of the K combinator is just const.

In fact i am trying to express the function \f x -> f x x using standard functions, but cannot think of any standard non-linear function to start with (that is a function that uses its argument more than once).

• duplode: \f x -> f x x is join in the function monad.
• jberryman: I blogged about a link I noticed between the SK combinator calculus and applicative functors, and got some interesting comments from readers you might want to check out. See also more interesting comments to this answer
• Sassa NF: what is a standard function?
• Sassa NF: @duplode i wonder if that counts as defining it by equation
• Alexey: @SassaNF, i meant anything fairly standard, like (.), ($), possibly flip :).

Answer 1

s = (<*>) for the ((->) r) Applicative instance.

• Alexey: Sorry, what is ((->) r)?
• David Young: @Alexey It is all types r ->. Unfortunately, you can't do a section with a type operator in the same way you can with a normal operator. So, though you can do something like (10*), this isn't valid Haskell (r ->). Luckily, we do have a syntax that gives us an equivalent result: ((->) r). Note, however, that we cannot do the same with the second argument. This is actually intentionally forbidden (I think it makes type inference impossible in some cases), which is why we can't have type operator sections.
• David Young: @Alexey So, if we have a type synonym type Function a b = a -> b, then ((->) r) is equivalent to Function r.
• Alexey: So, r was just a type variable?
• Alexey: Impossibility to have something like (-> Int), is it because Haskell does not allow contravariant functors, by any chance?

Answer 2

Although it doesn't look like it at first, ap is the S combinator (and join is the combinator you're really after).

• Alexey: Thanks, this is helpful. I think i will accept the other answer however because of the title of my question and since Applicative seems to be more general than Monad.
• Alexey: In fact, maybe Monad being more restrictive than Applicative, your answer is actually better.

Answer 3

It can also be used (=<<), (>>=).

And they are included in Prelude

instance Monad ((->) r) where 
 return = const
 f >>= k = \ r -> k (f r) r 

Answer 4

To me it's only understandable when writing out types out as follows:

The Wiki notation of the S combinator is

Sxyz = xz(yz)

Think of x as a function of two arguments, and y as one with one arguments, and z as a value. The value z is passed into y; that result together with z is passed into x.

The definition of <*> is

(<*>) :: f (a -> b) -> f a -> f b

where f here is the Function functor ((->) r), which is just the prefix notation for the usual function type notation r -> .. So just expanding the type results (hiding some -> arrows for simplicity) in

 (<*>) :: f (a -> b) -> f a -> f b
 f (a -> b) f a f b
 r->(a -> b) r->a r->b
 r-> a -> b r->a r->b
 ^^^^^^^^^^ ^^^^ ^
 x (2args) y (1arg) z (value)

As in the S combinator, the value z (corresponds to r) is passed to y (corresponds to r -> a); that result (corresponds to a) is passed together with z into x (corresponds to r -> a -> b) as the first argument. The final result corresponds to b.