康纳德在哈斯克尔打破了懒惰

Question

我正在尝试Cont monad,并发现以下问题.

1. 首先构造一个无限列表并将所有元素提升为Cont monad
2. 使用序列操作在无限列表中获取Cont monad.
3. 例如,当我们尝试使用头部运行monad时,它会在尝试扩展延续时陷入无限循环,并且永远不会调用头部.

代码如下所示:

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

那么这是Haskell中Cont monad实现的限制吗？如果是这样,我们如何改善这一点？

Answer 1

其原因是,即使值的头元素sequence someList只取决于第一elemenent someList,该效果的sequence someList一般可以依靠的全部效应someList(以及它对于大多数的单子).因此,如果我们想要评估head元素,我们仍然需要评估所有效果.

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

这同样适用Cont.在continuation 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.所以为了看看是什么head元素sequence someList中Cont,我们再次需要计算所有.

Answer 2

这不是Contmonad 的缺陷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>

有一些monad mapM将在无限的值列表中工作,特别是懒惰的StateTmonad和Identity,但它们是规则的例外.

通常,mapM/ sequence/ replicateM(没有尾随下划线)是反模式并且使用正确的解决方案pipes,这允许您构建有效的流,而不是尝试预先计算所有结果. 本pipes教程的开头部分描述了如何更详细地解决这个问题,但一般的经验法则是,每当你写下这样的内容时:

example1 = mapM f xs

example2 = sequence xs

只需将其转换为以下内容即可将其转换为惰性Producer:

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

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

使用上面的例子Either,你会写:

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

然后你可以懒惰地处理流而不生成所有元素:

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