使用toList不好嗎？

假設2個地圖使用toList不好嗎？

import qualified Data.Map as M 
sparse1, sparse2 :: M.Map Int Float 
sparse1 = M.fromList [(1,2.0),(10,3),(12,5),(100,7),(102,11)] 
sparse2 = M.fromList [(2,13.0),(11,17),(12,19),(101,23),(102,29)]

你如何定義一個優雅功能

combi :: M.Map Int Float -> M.Map Int Float -> Float

使得sparse2返回COMBI sparse1 414.0（= 5 * 19 + 11 * 29），因爲12和102是唯一的兩張地圖的共同鑰匙？沒有與名單優雅的（簡單而有效的）功能，因爲這些將嚴格下令：

combiList xs ys = cL xs ys 0 
cL [] _ acc = acc 
cL _ [] acc = acc 
cL ([email protected](k,r):xs) ([email protected](k',r'):ys) acc 
    | k < k' = cL xs  (y:ys) acc 
    | k == k' = cL xs  ys  (acc+r*r') 
    | k > k' = cL (x:xs) ys  acc

不過是

combi m1 m2 = combiList (M.toList m1) (M.toList m2)

一個好主意，知道名單是沒有在的剩下的更習慣代碼？如果不是，那麼如何在沒有toList的情況下高效地編寫combi？

來源

2010-10-05 sauf

使用的地圖fold和intersectWith是多一點優雅（可能更快）：

combi :: M.Map Int Float -> M.Map Int Float -> Float 
combi x y = M.fold (+) 0 $ M.intersectionWith (*) x y

combi sparse1 sparse2回報414.0達到目標。

如果您關心性能，請嘗試使用Data.IntMap：它應該比這裏的Data.Map快幾倍。

來源

2010-10-05 00:49:15

我同意它更優雅，但速度更快嗎？我不認爲在GHC中，由Map.intersectionWith生成的地圖和由Map.fold消耗的地圖是融合的，因此如果有許多公用密鑰，則此代碼可能會變慢。 – 2010-10-05 18:53:38

在這種情況下，我們無法從'Data.Map'中獲得非常好的性能。 'fold'和'intersectionWith'都是懶惰的，會導致額外的thunk被創建。 – tibbe 2011-04-28 13:08:51

使用toList不好嗎？

回答

相關問題