20

更新：好的，这个问题可能变得非常简单。

q <- mapM return [1..]

为什么这永远不会回来？

mapM 不会懒惰地处理无限列表吗？

下面的代码挂起。但是，如果我用 B 行替换 A 行，它就不再挂起。或者，如果我在 A 行前面加上“splitRandom $”，它也不会挂起。

Q1是：mapM不偷懒吗？否则，为什么用 B 行替换 A 行“修复此”代码？

Q2 是：为什么前面的 A 行和 splitRandom “解决”了这个问题？

import Control.Monad.Random
import Control.Applicative

f :: (RandomGen g) => Rand g (Double, [Double])
f = do
    b <- splitRandom $ sequence $ repeat $ getRandom
    c <- mapM return b -- A
    -- let c = map id b -- B
    a <- getRandom
    return (a, c)

splitRandom :: (RandomGen g) => Rand g a -> Rand g a
splitRandom code = evalRand code <$> getSplit

t0 = do
    (a, b) <- evalRand f <$> newStdGen
    print  a
    print (take 3 b)

该代码懒惰地生成一个无限的随机数列表。然后它生成一个随机数。通过使用 splitRandom，我可以在无限列表之前先评估后一个随机数。如果我在函数中返回 b 而不是 c，则可以证明这一点。

但是，如果我将 mapM 应用于列表，程序现在会挂起。为了防止这种挂起，我必须在 mapM 之前再次应用 splitRandom。我的印象是mapM可以偷懒

4

5 回答 5

32

好吧，有惰性，然后有惰性。mapM确实很懒惰，因为它没有做比它必须做的更多的工作。但是，请查看类型签名：

mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]

想想这意味着什么：你给它一个函数a -> m b和一堆as。常规map可以将它们变成一堆m bs，但不能将m [b]. 将bs 组合成一个[b]而不会妨碍 monad 的唯一方法是使用>>=将m bs 排序在一起以构造列表。

事实上，mapM正好等价于sequence . map。

一般来说，对于任何一元表达式，如果完全使用该值，>>=则必须强制通向该表达式的整个 s 链，因此sequence永远无法完成对无限列表的应用。

如果你想使用一个无界的单子序列，你要么需要显式的流程控制——例如，一个循环终止条件以某种方式烘焙到绑定链中，简单的递归函数喜欢mapM并且sequence不提供——或者一个步骤- 逐步顺序，如下所示：

data Stream m a = Nil | Stream a (m (Stream m a))

...这样您就可以根据需要强制使用尽可能多的 monad 层。

编辑::关于splitRandom，发生的事情是你传递给它一个Rand计算，用种子splitRandom得到评估，然后得到return结果。如果没有splitRandom，single 使用的种子getRandom必须来自对无限列表进行排序的最终结果，因此它会挂起。有了 extra splitRandom，使用的种子只需要穿过两个splitRandom调用，所以它可以工作。最终的随机数列表有效，因为此时您已经离开了Randmonad，没有任何东西取决于它的最终状态。

于 2010-07-17T04:49:33.210 回答
8

好的，这个问题可能变得非常简单。

q <- mapM 返回 [1..]

为什么这永远不会回来？

这不一定是真的。这取决于你所在的单子。

例如，使用 identity monad，您可以懒惰地使用结果，它可以正常终止：

newtype Identity a = Identity a

instance Monad Identity where
  Identity x >>= k = k x
  return = Identity

-- "foo" is the infinite list of all the positive integers
foo :: [Integer]
Identity foo = do
  q <- mapM return [1..]
  return q

main :: IO ()
main = print $ take 20 foo -- [1 .. 20]
于 2013-01-06T01:09:54.913 回答
7

mapM return [1..]这是一个不会终止的证明的尝试。让我们暂时假设我们在Identitymonad 中（这个论点也适用于任何其他 monad）：

mapM return [1..] -- initial expression
sequence (map return [1 ..]) -- unfold mapM
let k m m' = m >>= \x ->
             m' >>= \xs ->
             return (x : xs)
in foldr k (return []) (map return [1..]) -- unfold sequence

到目前为止，一切都很好...

-- unfold foldr
let k m m' = m >>= \x ->
             m' >>= \xs ->
             return (x : xs)
    go [] = return []
    go (y:ys) = k y (go ys)
in go (map return [1..])

-- unfold map so we have enough of a list to pattern-match go:
go (return 1 : map return [2..])
-- unfold go:
k (return 1) (go (map return [2..])
-- unfold k:
(return 1) >>= \x -> go (map return [2..]) >>= \xs -> return (x:xs)

回想一下，return a = Identity a在 Identity monad 和(Identity a) >>= f = f aIdentity monad 中。继续：

-- unfold >>= :
(\x -> go (map return [2..]) >>= \xs -> return (x:xs)) 1
-- apply 1 to \x -> ... :
go (map return [2..]) >>= \xs -> return (1:xs)
-- unfold >>= :
(\xs -> return (1:xs)) (go (map return [2..]))

请注意，此时我们很想申请\xs，但我们还不能！相反，我们必须继续展开，直到我们有一个可以应用的值：

-- unfold map for go:
(\xs -> return (1:xs)) (go (return 2 : map return [3..]))
-- unfold go:
(\xs -> return (1:xs)) (k (return 2) (go (map return [3..])))
-- unfold k:
(\xs -> return (1:xs)) ((return 2) >>= \x2 ->
                         (go (map return [3..])) >>= \xs2 ->
                         return (x2:xs2))
-- unfold >>= :
(\xs -> return (1:xs)) ((\x2 -> (go (map return [3...])) >>= \xs2 ->
                        return (x2:xs2)) 2)

此时，我们仍然不能申请\xs，但我们可以申请\x2。继续：

-- apply 2 to \x2 :
(\xs -> return (1:xs)) ((go (map return [3...])) >>= \xs2 ->
                         return (2:xs2))
-- unfold >>= :
(\xs -> return (1:xs)) (\xs2 -> return (2:xs2)) (go (map return [3..]))

\xs 现在我们已经到了一个既不能也 \xs2不能减少的地步！我们唯一的选择是：

-- unfold map for go, and so on...
(\xs -> return (1:xs))
  (\xs2 -> return (2:xs2))
    (go ((return 3) : (map return [4..])))

所以你可以看到，因为foldr，我们正在构建一系列要应用的函数，从列表的末尾开始，然后按照我们的方式进行备份。因为在每一步输入列表都是无限的，这种展开永远不会终止，我们也永远不会得到答案。

如果您查看此示例，这是有道理的（从另一个 StackOverflow 线程借来的，我目前找不到哪个）。在以下单子列表中：

mebs = [Just 3, Just 4, Nothing]

我们希望sequence捕获Nothing并返回整个事情的失败：

sequence mebs = Nothing

但是，对于此列表：

mebs2 = [Just 3, Just 4]

我们希望序列给我们：

sequence mebs = Just [3, 4]

换句话说，sequence 必须查看整个单子计算列表，将它们串在一起，然后全部运行，才能得出正确的答案。没有sequence看到整个列表就无法给出答案。

注意：此答案的先前版本断言foldr从列表的后面开始计算，并且在无限列表上根本不起作用，但这是不正确的！如果您传递给的运算符foldr在其第二个参数上是惰性的，并使用诸如列表之类的惰性数据构造函数生成输出，foldr则将很高兴与无限列表一起使用。参见foldr (\x xs -> (replicate x x) ++ xs) [] [1...]示例。但我们的 operator 并非如此k。

于 2010-07-17T22:31:34.597 回答
4

这个问题很好地展示了 IO Monad 和其他 Monad 之间的区别。在后台，mapM 在所有列表元素之间使用绑定操作 (>>=) 构建表达式，以将一元表达式列表转换为列表的一元表达式。现在，IO monad 的不同之处在于 Haskell 的执行模型是在 IO Monad 的绑定期间执行表达式。这正是最终迫使（在一个纯粹的懒惰世界中）执行某些事情的原因。

所以 IO Monad 在某种程度上是特殊的，它使用 bind 的序列范式来实际强制执行每个步骤，这就是我们的程序最终执行任何事情的原因。其他单子是不同的。它们具有绑定运算符的其他含义，具体取决于 Monad。IO 实际上是在绑定中执行事物的一个 Monad，这就是 IO 类型是“动作”的原因。

以下示例显示其他 Monad 不强制执行，例如 Maybe monad。最后，这导致 IO Monad 中的 mapM 返回一个表达式，该表达式 - 在执行时 - 在返回最终值之前执行每个单个元素。

有关于这方面的好论文，从这里开始或搜索指称语义和 Monads：解决尴尬的小队：http ://research.microsoft.com/en-us/um/people/simonpj/papers/marktoberdorf/mark.pdf

Maybe Monad 的例子：

模块主要在哪里

fstMaybe :: [Int] -> Maybe [Int] fstMaybe = mapM (\x -> if x == 3 then Nothing else Just x)

main = do let r = fstMaybe [1..] return r

于 2015-01-11T16:16:12.080 回答
1

让我们在更一般的背景下讨论这个问题。

正如其他答案所说，这mapM只是sequence和的组合map。所以问题是为什么在某些ssequence中是严格的。但是Monad，这不仅限于s，因为我们在大多数情况下共享相同的实现。MonadsApplicativesequenceAsequence

现在看一下（专门用于列表的）类型签名sequenceA：

sequenceA :: Applicative f => [f a] -> f [a]

你会怎么做？你得到了一个清单，所以你想foldr在这个清单上使用。

sequenceA = foldr f b where ...
  --f :: f a -> f [a] -> f [a]
  --b :: f [a]

既然f是一个Applicative，你就知道bcoule 是什么 - pure []。但什么是f？显然它是一个提升版本(:)：

(:) :: a -> [a] -> [a]

所以现在我们知道如何sequenceA工作了：

sequenceA = foldr f b where
  f a b = (:) <$> a <*> b
  b = pure []

或者

sequenceA = foldr ((<*>) . fmap (:)) (pure [])

假设给你一个惰性列表(x:_|_)。上面sequenceA给出的定义

sequenceA (x:_|_) === (:) <$> x <*> foldr ((<*>) . fmap (:)) (pure []) _|_
                  === (:) <$> x <*> _|_

所以现在我们看到问题被简化为考虑天气f <*> _|_是否_|_存在。显然 if fis strict this is _|_，但如果 f 不严格，为了允许停止评估，我们要求<*>自己是非严格的。

因此，应用函子具有sequenceA停止的标准将是<*>运算符是非严格的。一个简单的测试是

const a <$> _|_ === _|_      ====> strict sequenceA
-- remember f <$> a === pure f <*> a

如果我们在谈论Moands，则标准是

_|_ >> const a === _|_ ===> strict sequence
于 2014-07-14T05:31:37.137 回答