Where did bind come from?

haskell, monads, pointfree, types

Solution

Here's a short, straightforward combinators-style derivation:

iterate f x 
   = x : iterate f (f x) 
   = (:) x ((iterate f . f) x)
   = ap (:) (iterate f . f) x            -- ap g f x = g x (f x)       (1)
   = ap (:) ((.) (iterate f) f) x
   = ap (:) ( ((.) =<< iterate) f) x     -- (g =<< f) x = g (f x) x    (2)
   = ap (:) ( ((.) =<<) iterate f) x
   = ((ap (:) .) . ((.) =<<)) iterate f x 
       -- ((f .) . g) x y = (f .) (g x) y = (f . g x) y = f (g x y)    (3)

so, by eta-contraction,

iterate = ((ap (:) .) . ((.) =<<)) iterate
        = fix ((ap (:) .) . ((.) =<<))    -- fix f = x where x = f x   (4)

QED. (1) and (2) come from what you ask about, functions as monads, already explained in Chris's answer:

  ap :: (Monad m) => m (a->b) ->   m a  ->  m b              m ~ (r ->)
  that's            (r->a->b) -> (r->a) -> r->b 
  so            ap     g           f       x   = g x (f x)

  (=<<) :: (Monad m) => (a-> m b) ->   m a  ->  m b          m ~ (r ->)
  that's                (a->r->b) -> (r->a) -> r->b
  so            (=<<)      g           f       x   = g (f x) x

(3) is discussed e.g. here and here at length.

Problem

Using lambdabot's pl plug-in, ``` let iterate f x = x : iterate f (f x) in iterate ``` is converted to ``` fix ((ap (:) .) . ((.) =<<)) ``` What does the `(=<<)` mean here? I thought that it is only used with monads.

Original source

Related problems