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

I [blogged](http://brandon.si/code/do-applicative-functors-generalize-the-s-k-combinators/) 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](http://stackoverflow.com/a/7403708/176841) — jberryman, Apr 15 '14 at 23:07
@SassaNF, i meant anything fairly standard, like `(.)`, `($)`, possibly `flip` :). — Alexey, Apr 16 '14 at 09:15
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. — Rein Henrichs, Apr 16 '14 at 22:02
@ReinHenrichs: i know that it is not the **S** combinator. What is a *free theorem*? — Alexey, Apr 16 '14 at 22:11
@Alexey 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 http://stackoverflow.com/questions/12421085/good-introduction-to-free-theorems. — Rein Henrichs, Apr 16 '14 at 22:39
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: http://stackoverflow.com/questions/10217931/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. — Rein Henrichs, Apr 16 '14 at 22:43
@Alexey 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. — Rein Henrichs, Apr 16 '14 at 23:12
See also [The Monad Reader Issue 17](https://themonadreader.files.wordpress.com/2011/01/issue17.pdf): The Reader Monad and Abstraction Elimination. — Petr, Jul 20 '15 at 12:36

score 32 · Accepted Answer · edited Apr 16 '14 at 21:11

32

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

edited Apr 16 '14 at 21:11

Alexey

3,843
6
30
44

answered Apr 15 '14 at 22:00

David Young

10,713
2
33
47

Sorry, what is `((->) r)`? – Alexey Apr 16 '14 at 23:22
1

@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 Apr 16 '14 at 23:55
1

@Alexey So, if we have a type synonym `type Function a b = a -> b`, then `((->) r)` is equivalent to `Function r`. – David Young Apr 16 '14 at 23:56
So, `r` was just a type variable? – Alexey Apr 16 '14 at 23:59
Impossibility to have something like `(-> Int)`, is it because Haskell does not allow contravariant functors, by any chance? – Alexey Apr 17 '14 at 00:04
@Alexey: Yeah, `r` is a type variable. Actually, Haskell does have (or can have) contravariant functors (http://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. – David Young Apr 17 '14 at 00:23

score 22 · Answer 2 · answered Apr 15 '14 at 21:59

22

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

answered Apr 15 '14 at 21:59

Daniel Wagner

145,880
9
220
380

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 Apr 16 '14 at 23:23
In fact, maybe `Monad` being more restrictive than `Applicative`, your answer is actually *better*. – Alexey Apr 17 '14 at 08:56

Daishi Nakajima · Answer 3 · 2015-07-21T07:19:58.643

0

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

And they are included in Prelude

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

edited Jul 21 '15 at 07:19

answered Jul 20 '15 at 11:26

Daishi Nakajima

1,932
18
26

S combinator in Haskell

3 Answers3

Linked