Ist es schlecht ToList zu verwenden?

Question

Angenommen 2 Karten

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)] 

Wie Sie eine elegante Funktion

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

so dass combi sparse1 definieren sparse2 414,0 zurück (= 5 * 19 + 11 * 29), weil 12 und 102 die einzigen sind gemeinsame Schlüssel der beiden Karten? Es ist eine elegante (einfach und effizient) Funktion mit Listen, da diese würden streng bestellt werden:

combiList xs ys = cL xs ys 0 
cL [] _ acc = acc 
cL _ [] acc = acc 
cL (x@(k,r):xs) (y@(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 

Aber ist

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

eine gute Idee zu wissen, die Listen sind nicht mehr verwenden in dem Rest der Code? Und wenn nicht, wie würden Sie effizient Combi ohne toList schreiben?

Answer 1

Mit fold und intersectWith auf den Karten ist ein bisschen eleganter (und wahrscheinlich schneller):

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

combi sparse1 sparse2 kehrt 414.0 nach Wunsch.

Und wenn Sie über die Leistung, versuchen Sie es mit : Es sollte mehrere Male schneller sein als Data.Map hier.