CODEWITHSUNDEEP
haskellcombinatorss-combinator
Alexey
Alexey

Reputation: 4071

S combinator in Haskell

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

Upvotes: 17

Views: 5323

Answers (4)

manews
manews

Reputation: 410

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.

Upvotes: 0

Daishi Nakajima
Daishi Nakajima

Reputation: 1942

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

And they are included in Prelude

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

Upvotes: 0

David Young
David Young

Reputation: 10793

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

Upvotes: 33

Daniel Wagner
Daniel Wagner

Reputation: 153172

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

Upvotes: 22

Related Questions