厳密な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では）。

DataArray.Unboxed以外のaccumArrayの厳密なバージョンはありますか？それとも、私が欲しいことをする良い方法がありますか？

Answer 1

厳密には、サンクが作成されていないことを必ずしも意味しているわけではなく、引数がbottomの場合も結果がbottomであることを意味します。しかし、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 

を使用することができ、サンクが小さく維持されているので、スタックオーバーフローはありません。しかし、リストには多くのスペースがありますので、リストが長すぎるとヒープが枯渇する可能性があります。それは使用上の結合機能の結果を強制insertWith'、付属していますので

別のオプションは、（containersのバージョンが0.4.1.0である場合や、またはData.IntMap）配列の代わりにData.Mapを使用することであろう。コードは、例えばMapを使用しての

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 -> a -> aを持っている必要があります

• あることができます。
• 更新はO（1）ではなくO（ログサイズ）です。したがって、大きなヒストグラムの場合、更新はかなり遅くなります。
• MapおよびIntMapには、ブックよりもオーバーヘッドがあるため、配列よりも多くのスペースが使用されます。しかし、更新のリストがインデックスの数と比較して大きい場合、その差は無視されます（オーバーヘッドはキーの値とは無関係にキーごとにkワードです）。この場合、値のサイズはそれぞれ更新。