16

考虑以下示例:

safeMapM f xs = safeMapM' xs []
    where safeMapM' []     acc = return $ reverse acc
          safeMapM' (x:xs) acc = do y <- f x
                                    safeMapM' xs (y:acc)

mapM return largelist      -- Causes stack space overflow on large lists
safeMapM return largelist  -- Seems to work fine

在大型列表上使用mapM会导致堆栈空间溢出,而safeMapM似乎工作正常(使用 GHC 7.6.1 和-O2)。但是我无法safeMapM在 Haskell 标准库中找到类似的函数。

mapM它仍然被认为是使用(或sequence就此而言)的好习惯吗?
如果是这样,为什么尽管存在堆栈空间溢出的危险,但仍将其视为良好做法?
如果不是,您建议使用哪种替代方案?

4

3 回答 3

9

正如 Niklas B. 一样, 的语义mapM是有效右折叠的语义,并且它在比翻转版本更多的情况下成功终止。一般来说,mapM这更有意义,因为我们很少会想要在庞大的数据列表上制作结果生成图。更常见的是,我们想要评估这样一个效果列表,在这种情况下mapM_,和sequence_会丢弃结果,通常是推荐的。

编辑:换句话说,尽管问题中提出了问题,的,mapM并且sequence是常用的并且通常被认为是良好的做法。

于 2013-03-21T17:09:11.823 回答
7

如果是这样,为什么尽管存在堆栈空间溢出的危险,但仍将其视为良好做法?如果不是,您建议使用哪种替代方案?

如果要在生成列表元素时对其进行处理,请使用pipesconduit。两者都不会建立中间列表。

我会指路pipes,因为那是我的图书馆。我将首先IO从用户输入在 monad 中生成的无限数字列表开始:

import Control.Proxy

infiniteInts :: (Proxy p) => () -> Producer p Int IO r
infiniteInts () = runIdentityP $ forever $ do
    n <- lift readLn
    respond n

现在,我想在它们生成时打印它们。这需要定义一个下游处理程序:

printer :: (Proxy p) => () -> Consumer p Int IO r
printer () = runIdentityP $ forever $ do
    n <- request ()
    lift $ print n

现在我可以连接ProducerConsumer使用(>->),并使用运行结果runProxy

>>> runProxy $ infiniteInts >-> printer
4<Enter>
4
7<Enter>
7
...

然后它将从用户那里读取Ints 并将它们回显到控制台,因为它们在生成时不会在内存中保存多个元素。

所以通常如果你想要一个有效的计算来生成一个元素流并立即使用它们,你不想要mapM. 使用适当的流媒体库。

如果你想了解更多pipes,那么我推荐阅读教程

于 2013-03-21T18:00:28.663 回答
-1

如果你想留在懒惰的阵营,lazyio包可以让你懒惰地处理输入列表。代替

mapM f

你写

import qualified System.IO.Lazy as LazyIO

LazyIO.run . mapM (LazyIO.interleave . f)

没有堆栈溢出了。

于 2016-12-14T20:55:46.010 回答