我怎样才能得到一个严格的accumArray？
我有一个键值对的列表，我想计算每个键出现的次数以及它出现的值，但是当我尝试时，出现堆栈溢出。 以下是我正在运行的代码的简化版本：
import Array
add (n, vals) val = n `seq` vals `seq` (n+1,val:vals)
histo = accumArray add (0,[]) (0,9) [(0, n) | n <- [0..5000000]]
main = print histo
当我用'ghc -O'编译这个并运行它时，我得到“堆栈空间溢出：当前大小8388608字节。”
我想我知道发生了什么：accumArray与foldl具有相同的属性，所以我需要一个严格版本的accumArray。 不幸的是，我发现的唯一一个是Data.Array.Unboxed，它不适用于列表数组。
该文档说，当累积函数严格时，accumArray应该也是，但我无法得到这个工作，并且这里的讨论声称文档是错误的（至少对于GHC）。
除Data.Array.Unboxed中的那个以外，是否有accumArray的严格版本？ 或者有更好的方法去做我想做的事吗？
那么严格并不一定意味着没有创建thunk，它只是意味着如果一个参数是最低的，结果也是最低的。 但是accumArray并不是那么严格，它只是在数组出现accumArray将其写入数组。 它不能做任何其他事情，因为它必须允许可以从中间底部产生定义值的非严格函数。 并且严格性分析器不能重写它，因此如果它是严格的，那么在每次写入时累积函数将被评估为WHNF，因为这会以相当激烈的方式改变程序的语义（包含一些底部与底部的数组） 。
也就是说，我同意在几个领域有不幸的缺乏严格和热切的职能。
对于你的问题，你可以使用更大的堆栈（ +RTS -K128M在这里没有足够的，但是256M），或者你可以使用
import Data.Array.Base (unsafeRead, unsafeWrite)
import Data.Array.ST
import GHC.Arr
strictAccumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(i,a)] -> Array i e
strictAccumArray fun ini (l,u) ies = case iar of
Array _ _ m barr -> Array l u m barr
where
iar = runSTArray $ do
let n = safeRangeSize (l,u)
stuff = [(safeIndex (l,u) n i, e) | (i, e) <- ies]
arr <- newArray (0,n-1) ini
let go ((i,v):ivs) = do
old <- unsafeRead arr i
unsafeWrite arr i $! fun old v
go ivs
go [] = return arr
go stuff
通过严格的写入，thunk被保持为小，所以没有堆栈溢出。 但要小心，列表占用大量空间，所以如果列表太长，可能会导致堆栈耗尽。
另一种选择是使用Data.Map （或Data.IntMap ，如果容器的版本是0.4.1.0或更高版本）而不是数组，因为insertWith'会强制使用组合函数的结果。 代码可以是例如
import qualified Data.Map as M -- or Data.IntMap
import Data.List (foldl')
histo :: M.Map Int (Int,[Int]) -- M.IntMap (Int,[Int])
histo = foldl' upd M.empty [(0,n) | n <- [0 .. 15000000]]
where
upd mp (i,n) = M.insertWith' add i (1,[n]) mp
add (j,val:_) (k,vals) = k `seq` vals `seq` (k+j,val:vals)
add _ pr = pr -- to avoid non-exhaustive pattern warning
使用Map缺点是
a -> a -> a ，所以在你的情况下它需要更复杂一些。 Map和IntMap有一些记账开销，所以会比数组使用更多的空间。 但是，如果更新列表与索引的数量相比较大，则在这种情况下，差异将可以忽略不计（开销是每个键的k字，与值的大小无关），其中值的大小随着每个更新。 上一篇: How can I get a strict accumArray?
下一篇: How to forward geocode in Python without Internet connection from scripts?