Załóżmy 2 MapyCzy korzystanie z toList jest złe?
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)]
Jak zdefiniować elegancką funkcję
combi :: M.Map Int Float -> M.Map Int Float -> Float
takie, że combi sparse1 sparse2 zwraca 414,0 (= 5 * 19 + 11 * 29), ponieważ 12 i 102 są jedynym wspólne klucze dwóch map? Jest to elegancki (proste i wydajne) funkcja z listami od tych, byłaby ściśle uporządkowane:
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
Ale jest
combi m1 m2 = combiList (M.toList m1) (M.toList m2)
dobrym pomysłem wiedząc wykazy nie są już używane w pozostałej części kod ? A jeśli nie, to jak wydajnie pisać kombi bez toList?
Zgadzam się, że jest bardziej elegancki, ale czy jest szybszy? Nie sądzę, że w GHC generowanie mapy przez Map.intersectionWith i konsumpcja mapy przez Map.fold są połączone, a zatem kod ten może być wolniejszy, jeśli istnieje wiele wspólnych kluczy. –
Nie możemy uzyskać naprawdę dobrej wydajności z 'Data.Map' w tym przypadku. 'Fold' i' intersectionWith' są leniwe i spowodują powstanie dodatkowych thunków. – tibbe