haskell - 如何获得严格的 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 也应该是，但我不能让它工作，讨论 here声称文档错误(至少对于 GHC)。

除了 Data.Array.Unboxed 中的 accumArray 之外，还有严格版本的 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 保持较小，因此没有堆栈溢出。但请注意，列表占用大量空间，因此如果您的列表太长，您可能会遇到堆耗尽。

另一种选择是使用 Data.Map (或 Data.IntMap ，如果 containers 的版本是 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 ，所以在你的情况下它需要更复杂一些。

更新是 O(log size) 而不是 O(1)，因此对于大直方图，它会相当慢。

Map s 和 IntMap s 有一些记账开销，因此这将使用比数组更多的空间。但是，如果更新列表与索引数量相比很大，则差异将可以忽略不计(开销是每个键的 k 个字，与值的大小无关)在这种情况下，值的大小会增长每次更新。