Это плохо использовать 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

, такую, что combi 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 здесь.