Плохо ли использовать toList?

Question

Пусть 2 Карты

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 

таким образом, что комби sparse1 sparse2 возвращает 414,0 (= 5 * 19 + 11 * 29), так как 12 и 102 являются единственными общие ключи двух карт? Существует элегантный (простой и эффективный) функция со списками, так как те будут строго приказал:

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 

Но

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

хорошая идея не зная, что списки не больше используется в остальной части код? А если нет, как бы вы эффективно записывали combi без toList?

Answer 1

Использование 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 здесь.