haskell - 绑定(bind)来自哪里？

Question

使用lambdabot的pl插件，

let iterate f x = x : iterate f (f x) in iterate

转换为

fix ((ap (:) .) . ((.) =<<))

(=<<)在这里是什么意思？我以为它仅用于单子(monad)。

Answer 1

这是一个简短，直接的combinators风格派生:

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)

因此，通过eta收缩，

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

QED。 (1)和(2)来自您的要求，起了Monad的作用，已经在Chris的答案中进行了解释:

  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)例如 here和 here的长度。