Haskell:IORefs的表现

Question

我一直在尝试在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.是否有任何阻止这种增长的技巧,特别是在太空？我经常需要IORef非原始类型的s Int,并且假设一个人IORef会像常规thunk一样使用额外的指针,但我的直觉似乎是错误的.

我已经尝试了一个带有解压缩的专用列表类型IORef,但没有显着差异.

Answer 1

这很可能不是关于IORef,而是关于严格性.IOmonad中的操作是串行的 - 所有先前的操作必须在下一个操作开始之前完成.所以

mapM newIORef list

IORef在读取任何内容之前产生一百万秒.

然而,

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

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

如果您想要更公平的比较,请使用严格map:

map' :: (a -> b) -> [a] -> [b]
map' f [] = []
map' f (x:xs) = (f x:) $! map' f xs

Answer 2

问题在于你的使用mapM,它在时间和空间上总是在大型列表上表现不佳.正确的解决方案是使用mapM_和融合中间列表(>=>):

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秒的恒定空间运行.