为什么Haskell序列函数不能懒惰或为什么递归单子函数不能懒惰 [英] Why the Haskell sequence function can't be lazy or why recursive monadic functions can't be lazy

问题描述

有了根据宽度优先的顺序列出目录中的所有内容导致效率低下，我了解到，低效率是由递归monad函数的奇怪行为造成的。

尝试

  sequence $ map return [1 ..] :: [[Int]] 
 sequence $ map return [1 ..] :: Maybe [Int] 
  

和ghci将陷入无穷无尽的计算中。如果我们更多地重写序列函数如下所示：

  sequence'[] = return [] 
 sequence'（m：ms）= do {X< -m; xs< -sequence'ms;返回（x：xs）} 
  

并尝试：

 序列'$ map return [1 ..] :: [[Int]] 
序列'$ map return [1 ..] :: Maybe [Int] 
  

我们得到相同的情况，一个无限循环。

尝试一个有限列表

  sequence'$ map return [1 ..] :: Maybe [Int] 
  

它会弹出预期结果只需[1,2,3,4。 。] 在长时间等待之后。

根据我们的尝试，我们可以得出这样的结论，尽管序列的定义似乎如果我们定义了一个函数，那么这个函数是非常严格的，并且必须在序列的结果之前打印所有的数字。

  iterateM :: Monad m => （a  - > m a） - > a  - > m [a] 
 iterateM fx =（fx）>> = iterateM0 f>> = return。（x :) 
  

并尝试

  iterateM（>> =（+ 1））0 
  

然后发生无尽的计算。

我们都知道，非单点迭代就像上面的iterateM一样定义，但为什么迭代是惰性的，迭代M是严格的。
从上面我们可以看出，iterateM和sequence'都是递归单子函数。有一些奇怪的递归单子函数

解决方案 div>

问题不在于 sequence 的定义，它是底层monad的操作。尤其是，monad的>> = 操作的严格性决定了 sequence 的严格性。 p>



对于一个足够懒惰的monad，完全可以在无限列表上运行 sequence ，并逐渐消耗结果。考虑：



  Prelude> ：m + Control.Monad.Identity 
 Prelude Control.Monad.Identity> runIdentity（sequence $ map return [1 ..] :: Identity [Int]）
  

和列表将根据需要递增打印（消耗）。



使用 Control.Monad.State.Strict 和 Control.Monad.State.Lazy ：

   -  - 将打印列表
 Prelude Control.Monad.State.Lazy> evalState（sequence $ map return [1 ..] :: State（）[Int]）（）
  -  loops 
 Prelude Control.Monad.State.Strict> evalState（sequence $ map return [1 ..] :: State（）[Int]）（）
  

在 IO monad中，>> = 在定义上是严格的，因为这个严格性恰好是必要的属性以启用效果排序的推理。我认为@ jberryman的回答很好地证明了strict >> = 的含义。对于 IO 和其他具有严格>> = 的monad，列表中的每个表达式必须在 sequence 可以返回。有了无限的表达式列表，这是不可能的。

With the question Listing all the contents of a directory by breadth-first order results in low efficiencyI learned that the low efficiency is due to a strange behavior of the recursive monad functions.

Try

sequence $ map return [1..]::[[Int]]
sequence $ map return [1..]::Maybe [Int]

and ghci will fall into an endless calculation.

If we rewrite the sequence function in a more readable form like follows:

sequence' []     = return []
sequence' (m:ms) = do {x<-m; xs<-sequence' ms; return (x:xs)}

and try:

sequence' $ map return [1..]::[[Int]]
sequence' $ map return [1..]::Maybe [Int]

we get the same situation, an endless loop.

Try a finite list

sequence' $ map return [1..]::Maybe [Int]

it will spring out the expected result Just [1,2,3,4..] after a long time waiting.

From what we tried,we can come to the conclusion that although the definition of sequence' seems to be lazy, it is strict and has to make out all the numbers before the result of sequence' can be printed.

Not only just sequence', if we define a function

iterateM:: Monad m => (a -> m a) -> a -> m [a]
iterateM f x = (f x) >>= iterateM0 f >>= return.(x:)

and try

iterateM (>>=(+1)) 0

then endless calculation occurs.

As we all know,the non-monadic iterate is defined just like the above iterateM, but why the iterate is lazy and iterateM is strict. As we can see from above, both iterateM and sequence' are recursive monadic functions.Is there some thing strange with recursive monadic functions

解决方案

The problem isn't the definition of sequence, it's the operation of the underlying monad. In particular, it's the strictness of the monad's >>= operation that determines the strictness of sequence.

For a sufficiently lazy monad, it's entirely possible to run sequence on an infinite list and consume the result incrementally. Consider:

Prelude>  :m + Control.Monad.Identity
Prelude Control.Monad.Identity> runIdentity (sequence $ map return [1..] :: Identity [Int])

and the list will be printed (consumed) incrementally as desired.

It may be enlightening to try this with Control.Monad.State.Strict and Control.Monad.State.Lazy:

-- will print the list
Prelude Control.Monad.State.Lazy> evalState (sequence $ map return [1..] :: State () [Int]) ()
-- loops
Prelude Control.Monad.State.Strict> evalState (sequence $ map return [1..] :: State () [Int]) ()

In the IO monad, >>= is by definition strict, since this strictness is exactly the property necessary to enable reasoning about effect sequencing. I think @jberryman's answer is a good demonstration of what is meant by a "strict >>=". For IO and other monads with a strict >>=, each expression in the list must be evaluated before sequence can return. With an infinite list of expressions, this isn't possible.

这篇关于为什么Haskell序列函数不能懒惰或为什么递归单子函数不能懒惰的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！