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

Sinaloa

\f x -> f x x is join in the function monad. – Myer

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 – Berserk

what is a standard function? – Wollastonite

@Myer i wonder if that counts as defining it by equation – Wollastonite

@SassaNF, i meant anything fairly standard, like (.), ($), possibly flip :). – Sinaloa

But \f x -> f x x is not the S combinator. The S combinator is \f g x -> f x (g x), which is a free theorem for its type. – Tresatrescha

@ReinHenrichs: i know that it is not the S combinator. What is a free theorem? – Sinaloa

@Sinaloa The short version is that there is a similarity between types and theorems called the Curry-Howard Correspondence. This means that finding a value of a given type is equivalent to finding a proof of the equivalent theorem. A free theorem is one for which a proof can be generated mechanically. In this case, given the type you mentioned, a value of that type (the function I mentioned) can be generated mechanically, thus "proving" the "theorem" for "free". See also #12421585. – Tresatrescha

In other words, \f g x -> f x (g x) is an existence proof that the type (a -> b -> c) -> (a -> b) -> a -> c is inhabited. This function can be generated mechanically, i.e. "for free", in a way that is explained here: https://mcmap.net/q/190386/-how-does-djinn-work. And, in fact, if you wanted to find a function (<*>) to use for for ((->) r, you could just ask Djinn to do the proof for you. – Tresatrescha

Thanks, i'll look into the Philip Wadler's paper. – Sinaloa

@Sinaloa Actually, what I'm referring to isn't really "free theorems", which is the generation of theorems for free. This is the generation of proofs "for free" (through an automatic decision procedure that makes use of the CH Correspondence). Sorry for the confusion. The Wadler paper is still fascinating though. – Tresatrescha

See also The Monad Reader Issue 17: The Reader Monad and Abstraction Elimination. – Tamtam

Answer 1

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

Aurochs

Sorry, what is ((->) r)? – Sinaloa

@Sinaloa 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. – Aurochs

@Sinaloa So, if we have a type synonym type Function a b = a -> b, then ((->) r) is equivalent to Function r. – Aurochs

So, r was just a type variable? – Sinaloa

Impossibility to have something like (-> Int), is it because Haskell does not allow contravariant functors, by any chance? – Sinaloa

@Alexey: Yeah, r is a type variable. Actually, Haskell does have (or can have) contravariant functors (hackage.haskell.org/package/contravariant). The reason it doesn't allow something like (-> Int) is that if it allowed you to rearrange type arguments however you want through partial type application, you would essentially have a full lambda calculus at a type level. This would make type inference impossible. – Aurochs

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

Granger

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. – Sinaloa

In fact, maybe Monad being more restrictive than Applicative, your answer is actually better. – Sinaloa

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  

Tahitian

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.

Publisher