Cont Monad打破了Haskell的懒惰

我正在尝试Cont monad，并发现以下问题。Cont Monad打破了Haskell的懒惰

首先构建一个无限列表，并解除所有元素的续单子
使用顺序操作以获取无限列表上的续单子。
例如，当我们尝试运行monad时，例如头部运行时，它会陷入无限循环，同时尝试扩展延续并且头部永远不会调用。

的代码看起来是这样的：

let inff = map (return :: a -> Cont r a) [0..] 
let seqf = sequence inff 
runCont seqf head

因此，这是在Haskell的单子续实施的限制？如果是这样，我们该如何改进？

来源

2014-02-22 Shiva Wu

可能的重复[为什么Haskell序列函数不能懒惰或为什么递归单子函数不能懒惰]（http://stackoverflow.com/questions/14494648/why-the-haskell-sequence-function - 懒惰或为什么递归一元函数） –

的原因是，即使的sequence someList的头元件的值仅取决于someList第一elemenent，所述效果的sequence someList通常可取决于所有someList的影响（对大多数单子来说也是如此）。因此，如果我们想评估头元素，我们仍然需要评估所有的影响。

例如，如果我们有Maybe值的列表中，sequence someList结果是Just仅当someList所有元素都Just。因此，如果我们尝试sequence一个无限列表，我们需要检查它的无限数量的元素，如果它们都是Just。

这同样适用于Cont。在继续monad中，我们可以随时从计算中逃脱并返回与迄今为止计算结果不同的结果。考虑下面的例子：

test :: (Num a, Enum a) => a 
test = flip runCont head $ 
    callCC $ \esc -> do 
     sequence (map return [0..100] ++ [esc [-1]])

或直接使用cont代替callCC：

test' :: (Num a, Enum a) => a 
test' = flip runCont head $ 
      sequence (map return [0..100] ++ [cont (const (-1))])

的test结果是刚刚-1。在处理了前100个元素之后，最终元素可以决定转义所有这一切，并返回-1。因此，为了看Cont中的head元素是什么，我们再次需要计算它们全部。

来源

2014-02-22 06:57:53

这不是Cont monad的缺陷，而是sequence。你可以得到类似的结果Either，例如：

import Control.Monad.Instances() 

xs :: [Either a Int] 
xs = map Right [0..] -- Note: return = Right, for Either 

ys :: Either a [Int] 
ys = sequence xs

你无法找回ys任何元素，直到它计算整个列表，这将永远不会发生。

另外，还要注意：sequence (map f xs) = mapM f xs，所以我们可以简化这个例子：

>>> import Control.Monad.Instances 
>>> mapM Right [0..] 
<Hangs forever>

有几个单子，其中mapM将值的无限清单开展工作，特别是懒惰StateT单子和Identity，但他们是规则的例外。

一般来说，mapM/sequence/replicateM（不带尾随下划线）是反模式和正确的解决办法是使用pipes，它允许你创建不尝试计算所有结果前面effectful流。 The beginning of the pipes tutorial介绍了如何在更详细解决这个问题，但一般的经验法则是，任何时候，你写的东西，如：

example1' = each xs >-> Pipes.Prelude.mapM f 

example2' = each xs >-> Pipes.Prelude.sequence

：

example1 = mapM f xs 

example2 = sequence xs

你可以只将其转化为改造成一个懒惰Producer

使用与Either上面的例子，你可以这样写：

>>> import Pipes 
>>> let xs = each [0..] >-> mapM Right :: Producer Int (Either a)()

然后你就可以懒惰地处理日而不产生所有元件E流：

>>> Pipes.Prelude.any (> 10) xs 
Right True

来源

2014-02-22 05:10:22

我认为调用mapM一般反模式有点苛刻。如果列表的长度没有限制（例如，来自用户输入），我会说这是不好的。但是，例如，在最多100个元素的列表中调用mapM并没有太大的错误。 – kosmikus

mapM函数根本不是反模式，只不过是反模式的效果。 – augustss

使用O（N^2）空间和时间复杂度的东西，当流O（N）解决方案存在时不会流，这是我眼中的反模式。此外，请注意OP在他们自己的话中将这种行为具体描述为有问题，所以这个陈述在这个问题的背景下是相关的。 –

Cont Monad打破了Haskell的懒惰

回答

相关问题