9

我一直在尝试在 Haskell 中编码一个需要使用大量可变引用的算法，但与纯粹的惰性代码相比，它（也许并不奇怪）非常慢。考虑一个非常简单的例子：

module Main where

import Data.IORef
import Control.Monad
import Control.Monad.Identity

list :: [Int]
list = [1..10^6]

main1 = mapM newIORef list >>= mapM readIORef >>= print
main2 = print $ map runIdentity $ map Identity list

在我的机器上运行 GHC 7.8.2，main1耗时 1.2 秒，使用 290MB 内存，而main2仅耗时 0.4 秒，仅使用 1MB。有什么技巧可以防止这种增长，尤其是在太空中？我经常需要IORefs 来表示与 不同的非原始类型Int，并假设 anIORef会像常规 thunk 一样使用附加指针，但我的直觉似乎是错误的。

我已经尝试过使用 unpacked 的特殊列表类型IORef，但没有显着差异。

4

3 回答 3

15

问题在于您对 的使用mapM，它在时间和空间上的大型列表上总是表现不佳。正确的解决方案是使用mapM_and来融合中间列表(>=>)：

import Data.IORef
import Control.Monad

list :: [Int]
list = [1..10^6]

main = mapM_ (newIORef >=> readIORef >=> print) list

它在恒定空间中运行并提供出色的性能，在我的机器上运行时间为 0.4 秒。

编辑：在回答您的问题时，您也可以这样做pipes以避免手动融合循环：

import Data.IORef
import Pipes
import qualified Pipes.Prelude as Pipes

list :: [Int]
list = [1..10^6]

main = runEffect $
    each list >-> Pipes.mapM newIORef >-> Pipes.mapM readIORef >-> Pipes.print

这在我的机器上以大约 0.7 秒的时间在恒定空间中运行。

于 2014-06-05T23:20:59.727 回答
14

这很可能不是关于IORef，而是关于严格性。monad 中的动作IO是连续的——所有先前的动作必须在下一个动作开始之前完成。所以

mapM newIORef list

在读取任何内容之前生成一百万IORef秒。

然而，

map runIdentity . map Identity
= map (runIdentity . Identity)
= map id

流非常好，所以我们print列表中的一个元素，然后生成下一个元素，等等。

如果您想要更公平的比较，请使用 strict map：

map' :: (a -> b) -> [a] -> [b]
map' f [] = []
map' f (x:xs) = (f x:) $! map' f xs
于 2014-06-05T19:22:42.313 回答
2

我发现解决方案的破解方法是使用惰性mapM代替，定义为

lazyMapM :: (a -> IO b) -> [a] -> IO [b]
lazyMapM f [] = return []
lazyMapM f (x:xs) = do
  y <-  f x
  ys <- unsafeInterleaveIO $ lazyMapM f xs
  return (y:ys)

这允许 monadic 版本在相同的 1MB 和相似的时间内运行。我希望惰性monad 可以在不使用, 作为函数的ST情况下更优雅地解决这个问题：unsafeInterleaveIO

main = print $ runST (mapM (newSTRef) list >>= mapM (readSTRef))

但这不起作用（您还需要使用unsafeInterleaveST），这让我想到了Control.Monad.ST.Lazy真正的懒惰。有人知道吗？:)

于 2014-06-05T23:04:49.723 回答