我怎样才能获得严格的accumArray？

Question

我有一个键值对列表,我想计算每个键出现的次数以及它出现的值,但是当我尝试时,我得到一个堆栈溢出.这是我正在运行的代码的简化版本:

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？或者有更好的方法来做我想要的吗？

Answer 1

好吧，严格并不一定意味着不创建 thunk，它只是意味着如果参数是底部，那么结果也是底部。但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 会保持很小，因此不会出现堆栈溢出。但请注意，列表会占用大量空间，因此如果列表太长，您可能会遇到堆耗尽问题。

另一种选择是使用 a 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

使用 a 的缺点Map是

• 组合函数必须具有 type a -> a -> a，因此在您的情况下它需要稍微复杂一些。
• 更新的时间复杂度为 O(log size) 而不是 O(1)，因此对于大直方图，它会慢得多。
• Maps 和IntMaps 有一些簿记开销，因此会比数组使用更多的空间。但是，如果更新列表与索引数量相比很大，则差异将可以忽略不计（开销是k每个键的字数，与值的大小无关），在这种情况下，值的大小随着每次更新而增长。