绑定来自哪里？

Question

使用lambdabot的pl插件,

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

转换为

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

这(=<<)意味着什么？我以为它只与monad一起使用.

Answer 1

让我们从定义开始

iterate f x = x : iterate f (f x) 

我们想将其转换为无点形式.我们可以一步一步地进行,但要了解它,您首先必须知道这一点

函数形成monad

或者,更具体地说,类型构造函数(->) r,您应该将其视为"函数来自类型r",或者(r ->)是monad.查看它的最佳方法是定义返回和绑定操作.monad的一般形式m是

return :: a -> m a
(>>=)  :: m a -> (a -> m b) -> m b

你有专门的功能

return :: a -> r -> a
(>>=)  :: (r -> a) -> (a -> r -> b) -> r -> b

你可以说服自己,唯一明智的定义是

return x = \r -> x -- equivalent to 'const x'
f >>=  g = \r -> g (f r) r

这完全等同于Reader monad,也称为环境monad.这个想法是你有一个额外的类型参数r(有时称为环境),它通过计算进行线程化 - 每个函数隐式地接收r作为附加参数.

现在我们知道了开始使我们的功能毫无意义所需的一切.

摆脱递归 fix

首先要删除递归引用iterate.我们可以使用fix具有定义的这个

fix :: (t -> t) -> t
fix f = f (fix f)

您可以将其fix视为规范递归函数,因为它可用于定义其他递归函数.标准习惯用法是定义一个g带有附加参数的非递归函数,该参数func表示您想要定义的函数.应用fix到g计算的固定点g,这是你想要的递归函数.

iterate = fix g where g func f x = x : func f (f x)

我们可以将其转换为lambda形式

iterate = fix (\func f x -> x : func f (f x))
        = fix (\func f x -> (:) x (func f (f x)))

第二行刚删除中缀:并用前缀替换它(:).既然没有自我引用,我们就可以继续了.

删除一些点 ap

我们可以ap用来提取引用x.类型ap是

ap :: (Monad m) => m (a -> b) -> m a -> m b

它在一些monadic上下文中使用一个函数,并将其应用于另一个monadic上下文中的值.请注意,这已经使用了函数(->) r形成monad 的事实!专门m为(->) r你得到

ap :: (r -> a -> b) -> (r -> a) -> (r -> b)

使类型解决的唯一方法是if ap(专用于函数)具有以下定义

ap f g = \r -> f r (g r)

这样你就可以使用第二个函数g来构建第一个函数的第二个参数f.请注意,这个定义ap是完全等价的组合子小号在SKI组合子演算.

对我们来说,这允许我们将参数提供x给第一个函数,(:)并使用另一个函数\y -> func f (f y)来构建第二个参数,即列表的尾部.作为一个加号,我们可以删除所有x使用eta减少的参考.

iterate = fix (\func f x -> ap (:) (\y -> func f (f y)) x)
        = fix (\func f   -> ap (:) (\y -> func f (f y))  )

现在,我们可以删除提及y为好,通过识别func f (f y)是刚刚组成func f和y.

iterate = fix (\func f   -> ap (:) (      func f . f)    )

通过与线程争论 (>>=)

现在我们有表达式(func f . f),或者(.) (func f) f如果我们使用前缀表示法.我们想将此描述为应用于某些函数f,但这需要我们f在两个地方处理表达式.

幸运的是,这正是monad实例(->) r所做的!如果你记得函数monad与读者monad完全等价,并且读者monad的工作是将一个额外的参数线程化到每个函数调用中,这就完全有意义了.

专门用于函数的bind的定义是

f >>= g = \r -> g (f r) r

该参数r首先穿过bind的左侧参数,其结果由右侧参数用于创建可以使用另一个参数的函数r.助记符是参数r首先穿过左参数,然后穿过右参数.

在我们的例子中,我们写到(.) (func f) f = (func >>= (.)) fget(使用eta减少)

iterate = fix (\func f   -> ap (:)  ((func >>= (.)) f))
        = fix (\func     -> ap (:) . (func >>= (.))   )

链接组成

最后,我们使用另一个技巧,重复组合,来拉出参数func.这个想法是,如果你有一个表达

f . g a

然后你可以用它替换它

f . g a = (.) f (g a)
        = (((.) f) . g) a
        = ((f .) . g) a

所以你把它表达为一个应用于参数的函数(准备eta减少!).在我们的情况下,这意味着进行更换

iterate = fix (\func     -> (ap (:) .) . (>>= (.)) func)
        = fix (            ((ap (:) .) . (>>= (.))     )

最后,删除内部括号并用(=<<)而不是(>>=)给出描述部分

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

这与lambdabot提出的表达方式相同.

Answer 2

这是一个简短、直接的组合器式推导：

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)

量子ED。（1）和（2）来自你所问的内容，作为单子发挥作用，克里斯的回答已经解释过：

  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) 例如在这里和这里详细讨论。