为什么Haskell序列函数不能是懒惰的,或者为什么递归monadic函数不能是懒惰的

Question

使用问题列出按广度优先顺序列出目录的所有内容效率低下我了解到效率低是由于递归monad函数的奇怪行为.

尝试

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

和ghci将陷入无休止的计算.

如果我们以更易读的形式重写序列函数,如下所示:

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

并尝试:

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

我们得到了相同的情况,无休止的循环.

尝试一个有限的列表

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

Just [1,2,3,4..]经过很长时间的等待,它会弹出预期的结果.

根据我们的尝试,我们可以得出结论,尽管序列的定义"似乎是懒惰的,但它是严格的,并且必须在序列结果之前得出所有数字"才能打印出来.

如果我们定义一个函数,不仅仅是序列'

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

并尝试

iterateM (>>=(+1)) 0

然后发生无休止的计算

众所周知,非monadic迭代的定义与上面的iterateM类似,但为什么迭代是惰性的,而iterateM是严格的.正如我们从上面所看到的,iterateM和sequence'都是递归的monadic函数.有一些奇怪的递归monadic函数

Answer 1

问题不在于定义sequence,而是底层monad的操作.特别是,monad >>=操作的严格性决定了它的严格性sequence.

对于一个足够懒惰的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:

-- 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]) ()

在IOmonad中,>>=根据定义是严格的,因为这种严格性正是实现效果排序推理所必需的属性.我认为@ jberryman的答案很好地证明了"严格>>="的含义.对于IO具有严格的其他monad,>>=必须在sequence返回之前评估列表中的每个表达式.使用无限的表达式列表,这是不可能的.

Answer 2

你不是很熟悉绑定的机制:

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

这是一个仅适用于3长度列表的序列实现:

sequence3 (ma:mb:mc:[]) = ma >>= (\a-> mb >>= (\b-> mc >>= (\c-> return [a,b,c] )))

你看我们如何在返回外部构造函数(即最外面的缺点,或者(:))之前"运行"列表中的每个"monadic动作" ？如果您不相信,请尝试以不同方式实施.

这是monad对IO有用的一个原因:当你绑定两个动作时,会有一个隐含的效果排序.

您还必须小心使用"懒惰"和"严格"这两个术语.这是真的sequence,你必须在最终结果被包装之前遍历整个列表,但是以下工作非常好:

Prelude Control.Monad> sequence3 [Just undefined, Just undefined, Nothing]
Nothing

Answer 3

Monadic sequence一般无法在无限列表上懒散地工作.考虑它的签名:

sequence :: Monad m => [m a] -> m [a]

它将论证中的所有monadic效果组合成单一效果.如果将其应用于无限列表,则需要将无限多个效果合并为一个.对于一些单子,有可能,对于一些单子,它不是.

作为一个例子,考虑sequence专门用于Maybe,如您在示例中所做的那样:

sequence :: [Maybe a] -> Maybe [a]

结果是Just ...iff数组中的所有元素都是Just ....如果有任何元素,Nothing那么结果是Nothing.这意味着,除非你检查所有输入的元素,你不能告诉如果结果是Nothing或Just ....

这同样适用于sequence专门到[]:sequence :: [[a]] -> [[a]].如果参数的任何元素是空列表,则整个结果是一个空列表,如in sequence [[1],[2,3],[],[4]].因此,为了评估sequence列表列表,您必须检查所有元素以查看结果的样子.

另一方面,专门用于Readermonad的序列可以懒惰地处理它的参数,因为对Readermonadic计算没有真正的"影响" .如果你定义

inf :: Reader Int [Int]
inf = sequence $ map return [1..]

也许

inf = sequence $ map (\x -> reader (* x)) [1..]

它可以懒散地工作,正如你可以通过调用看到的那样take 10 (runReader inf 3).