Haskell的mapM不是懒惰吗？

Question

更新:好的,这个问题可能非常简单.

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可以懒散

Answer 1

好吧,有懒惰,然后就是懒惰.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.

通常,对于任何monadic表达式,如果完全使用该值,则>>=必须强制导致表达式的整个s 链,因此应用于sequence无限列表无法完成.

如果你想用一个无界的一元序列的工作,你要么需要显式流量控制-例如,一个循环的终止条件烤成结合的链条不知何故,这就像简单的递归函数mapM和sequence不提供-或步逐步序列,如下所示:

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

...所以你只需要强制尽可能多的monad图层.

编辑::关于splitRandom,正在发生的事情是你传递一个Rand计算,用种子splitRandom得到评估,然后return结果.如果没有splitRandom,单个使用的种子getRandom必须来自无限列表排序的最终结果,因此它会挂起.使用额外的splitRandom,使用的种子只需要穿过两个splitRandom调用,所以它的工作原理.随机数的最终列表是有效的,因为你已经离开了Randmonad并且没有任何东西取决于它的最终状态.

Answer 2

这是尝试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线程,我目前找不到哪一个),这是有道理的.在以下monad列表中:

mebs = [Just 3, Just 4, Nothing]

我们期望sequence抓住Nothing并返回整个事情的失败:

sequence mebs = Nothing

但是,对于此列表:

mebs2 = [Just 3, Just 4]

我们希望序列给我们:

sequence mebs = Just [3, 4]

换句话说,sequence 必须查看整个monadic计算列表,将它们串在一起,并运行它们以便得出正确的答案.有没有办法,sequence可以给出一个答案没有看到整个列表.

Note: The previous version of this answer asserted that foldr computes starting from the back of the list, and wouldn't work at all on infinite lists, but that's incorrect! If the operator you pass to foldr is lazy on its second argument and produces output with a lazy data constructor like a list, foldr will happily work with an infinite list. See foldr (\x xs -> (replicate x x) ++ xs) [] [1...] for an example. But that's not the case with our operator k.

Answer 3

好的,这个问题可能非常简单.

q < - mapM返回[1 ..]

为什么这永远不会回来？

这不一定是真的.这取决于你所在的monad.

例如,使用标识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]