文章/答案/技术大牛

发布

问bind从哪里来的？
EN

Stack Overflow用户

提问于 2014-02-04 15:12:36

回答 3查看 459关注 0票数 10

使用lambdabot的pl插件，

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

被转换为

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

(=<<)在这里意味着什么？我以为它只和单子一起用。

haskell

types

monads

pointfree

回答 3

Stack Overflow用户

回答已采纳

发布于 2014-02-14 18:49:02

下面是一个简短、简单的组合子-style派生：

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)来自于你所问的，功能是单一的，在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)详细讨论了这里和这里。

票数 2

Stack Overflow用户

发布于 2014-02-04 15:58:41

让我们从定义开始

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

我们想把它转换成无点形式。我们可以一步一步地进行，但要理解它，你必须首先知道。

函数形成一个单元组

或者，更具体地说，类型构造函数(->) r (您应该把它看作是“来自类型r的函数”或(r ->) )是一个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

这完全等同于读者单读，也称为环境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)))

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

用ap删除一些点

我们可以使用ap提取对x的引用。ap的类型是

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

它在某个一元上下文中接受一个函数，并将其应用于另一个一元上下文中的值。请注意，这已经使用了函数(->) r形成一个monad的事实！专门化m到(->) r

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

使类型工作的唯一方法是如果ap (专门用于函数)具有以下定义

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

因此，您可以使用第二个函数g来构建第一个函数f的第二个参数。注意，ap的这个定义与滑雪组合子演算中的组合子S完全等价。

对于我们来说，这允许我们将参数x提供给第一个函数(:)，并使用另一个函数\y -> func f (f y)构建第二个参数，这是列表的尾部。作为一个加号，然后我们可以删除所有引用到x使用埃塔缩减。

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线程到表达式中。

幸运的是，这正是(->) r的monad实例所做的！如果您记住函数monad与reader完全等价，并且读取器monad的任务是在每个函数调用中线程一个额外的参数，那么这是完全有意义的。

专用于函数的绑定的定义是

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

参数r首先通过绑定的左侧参数进行线程化，其结果被右侧参数用来创建一个可以消耗另一个r的函数。助记符是参数r首先通过左参数线程化，然后通过右参数线程化。

在我们的例子中，我们编写了(.) (func f) f = (func >>= (.)) f来获取(使用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想出的同样的表达方式。

票数 13

Stack Overflow用户

发布于 2014-02-04 15:21:26

是的，这里的单变量是((->) a)：iterate f x显然是构造一个列表，所以iterate的类型是(a->a)->a->[a]，所以给定(a->a)，它生成(a->[a])

您可以看到，ap被赋予一个函数(:) :: a->[a]->[a]，它必须是m (a->b)，所以m在这里是(->) a。

(ap (:) .) . ((.) =<<) =
\f -> (ap (:) .) . ((.) =<<) $ f =
\f -> ap (:) . ((.) =<< f) = -- at this stage we can see =<< is of (->) a monad,
                       -- whose bind is the S-combinator: s f g x = f (g x) x
\f -> ap (:) . (f >>= (.)) =
\f g -> ap (:) (f g . g) = -- ok, ap is also the S-combinator with some
                           -- arguments swapped around
-- you see, for monad ((->) r), ap needs function of type (r->(a->b)) = (r->a->b)
-- whereas >>= needs (a->(r->b)) = (a->r->b) - the same function flipped
\f g -> (flip (:)) =<< (f g . g) =
\f g -> \x -> x : (f g $ g x)

这是两个参数的函数，a->(b->c)，所以当它被传递给fix :: (a->a)->a时，必须是a=(b->c)和fix (ap...) :: b->c。反过来，由于这一切都与iterate相同，所以必须是b->c = (x->x)->(x->[x])，所以是b=(x->x)，和c=(x->[x])

的确：

Prelude Control.Monad> :t ((ap (:) .) . ((.) =<<))
((ap (:) .) . ((.) =<<))
  :: (Monad ((->) (a -> b)), Monad ((->) a)) =>
     ((a -> b) -> b -> [a]) -> (a -> b) -> a -> [a]

它将在传递到b=a后绑定fix。

现在，fix向上面提供了第一个参数，如下所示：

fix h = let x = h x in x
hence, iterate = fix h = let iterate = h iterate in iterate 
-- supply iterate as the first
-- argument to the function passed to fix

所以我们有：

iterate =
fix (\f g -> \x -> x : (f g $ g x)) =
\g x -> x : (iterate g $ g x)

票数 4

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/21556158

复制

相似问题

问bind从哪里来的？
EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问bind从哪里来的？EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问bind从哪里来的？
EN