Haskell映射總和

是否有一個標準函數來對Haskell映射中的所有值進行求和？我的地圖讀取類似[（a，2），（b，4），（c，6）]？Haskell映射總和

基本上我想要做的是標準化的頻率分佈。所以上圖中鍵的值是a，b，c的計數。我需要將它們歸一化爲[（a，1/6），（b，1/3），（c，1/2）]

2011-12-18 atlantis

好問題。顯而易見的'foldl'解決方案對於在樹上進行求和是非常不可靠的。 – leftaroundabout 2011-12-18 21:36:04

其實，foldl''是我能想到的最好的方法; 'Data.Foldable.sum'將分別對每個分支進行求和，然後合併結果，但它不是平行或任何東西，所以這樣做沒有真正的好處（並且它有我在答案中提到的嚴格性問題）。一個並行的解決方案可能會很有趣，但可能只會爲足夠大的地圖帶來回報（此時您應該使用[unordered-containers]中的HashMap（http://hackage.haskell.org/package/unordered-containers）或類似的; Data.Map不是特別有效的結構）。 – ehird 2011-12-18 21:39:32

呃...我的是一個非常龐大的數據集。事實上，自從我閱讀關於Haskell結構的性能問題後，我決定不使用Hashtables。您提到的HashMap結構在用法上是否類似？ – atlantis 2011-12-18 22:32:32

您可以簡單地做Map.foldl' (+) 0（或M.foldl'，如果導入了Data.Map如M）。

這就像foldl' (+) 0 . Map.elems一樣，但效率稍高。（不要忘記撇號 - 使用foldl或foldr與標準數字類型（Int，Integer，Float，Double等）進行和會產生巨大的thunk，這將耗盡大量內存並可能導致程序溢出堆棧。）

然而，只有足夠新的版本containers（> = 0.4.2.0）包含Data.Map.foldl'，由於它與GHC你不應該cabal install升級。因此，除非您使用GHC 7.2或更高版本，否則foldl' (+) 0 . Map.elems是實現此目標的最佳方法。

您也可以使用Data.Foldable.sum，它可以在Foldable類型類型的任何實例上工作，但仍會在常用數字類型上構建大型thunk。

這裏有一個完整的例子：

normalize :: (Fractional a) => Map k a -> Map k a 
normalize m = Map.map (/ total) m 
    where total = foldl' (+) 0 $ Map.elems m

你需要導入到Data.List模塊使用foldl'。

來源

2011-12-18 21:01:17 ehird

let 
    total = foldr (\(_, n) r -> r + n) 0 l 
in map (\(x, y) -> (x, y/total) l

其中l是你的地圖。

來源

2011-12-18 21:02:41 Victor

簡單：

import qualified Data.Map as M 

sumMap = M.foldl' (+) 0 

normalizeMap m = 
    let s = sumMap m in 
    M.map (/ s) m 

main = do 
    let m = M.fromList [("foo", 1), ("bar", 2), ("baz", 6)] 
    (print . sumMap) m 
    (print . normalizeMap) m

打印：

9.0 
fromList [("bar",0.2222222222222222),("baz",0.6666666666666666),("foo",0.1111111111111111)]

來源

2011-12-18 21:07:14

這可能會給我一個'不在範圍內：Map.foldl'錯誤？我的進口看起來沒問題。 – atlantis 2011-12-18 22:31:07

@atlantis，那將是因爲你正在使用舊版本的容器庫。 – 2011-12-18 22:39:11

Haskell映射總和

回答

相關問題