13

通过按广度优先顺序列出目录的所有内容会导致效率低下的问题，我了解到效率低下是由于递归 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..]经过长时间的等待，它会弹出预期的结果。

通过我们的尝试，我们可以得出结论，虽然sequence'的定义看起来很懒惰，但它是严格的，必须在打印sequence'的结果之前把所有的数字都弄出来。

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

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

并尝试

iterateM (>>=(+1)) 0

然后发生无休止的计算。

众所周知，非monadic iterate的定义和上面的iterateM一样，但是为什么iterate是lazy的，iterateM是strict的。从上面我们可以看出，iterateM和sequence'都是递归monadic函数。递归monadic函数有什么奇怪的吗

4

3 回答 3

15

问题不在于 的定义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.Strictand可能会很有启发性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.

于 2013-01-24T08:30:33.670 回答
13

您不太了解绑定的机制：

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

这是仅适用于 3 长度列表的序列实现：

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

您看到我们必须如何“运行”列表中的每个“单子动作”，然后才能返回外部构造函数（即最外部的 cons 或(:)）？如果您不相信，请尝试以不同的方式实施它。

这是 monad 对 IO 有用的原因之一：当您绑定两个操作时，效果会隐含排序。

您还必须小心使用术语“懒惰”和“严格”。确实sequence，您必须遍历整个列表才能包装最终结果，但以下内容非常有效：

Prelude Control.Monad> sequence3 [Just undefined, Just undefined, Nothing]
Nothing
于 2013-01-24T06:36:03.880 回答
11

Monadicsequence通常不能在无限列表上懒惰地工作。考虑它的签名：

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

它将其论点中的所有一元效应组合成一个效应。如果将其应用于无限列表，则需要将无限数量的效果组合为一个。对于某些 monad，它是可能的，对于某些 monad，它不是。

例如，考虑sequence专门 to Maybe，就像您在示例中所做的那样：

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

结果是Just ...当且仅当数组中的所有元素都是Just .... 如果任何元素是，Nothing那么结果是Nothing。这意味着除非您检查输入的所有元素，否则您无法判断结果是Nothing还是Just ...。

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

另一方面，专门用于Readermonad 的序列可以懒惰地处理其参数，因为对 monad 的计算没有真正的“影响” Reader。如果你定义

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

也许

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

它会懒惰地工作，你可以通过调用take 10 (runReader inf 3).

于 2013-01-24T07:53:25.697 回答