Có xấu khi sử dụng toList không?

Question

Giả sử 2 Maps

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

Làm thế nào để bạn xác định một chức năng thanh lịch

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

mà sparse1 combi sparse2 trả 414,0 (= 5 * 19 + 11 * 29) vì 12 và 102 là những chỉ các phím chung của hai bản đồ? Có một chức năng thanh lịch (đơn giản và hiệu quả) với danh sách từ những người sẽ được ra lệnh nghiêm ngặt:

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 

Nhưng là

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

một ý tưởng tốt biết danh sách không được sử dụng nhiều hơn trong phần còn lại của mã? Và nếu không, làm thế nào bạn sẽ có hiệu quả viết combi mà không toList?

Answer 1

Sử dụng fold và intersectWith trên bản đồ là nhiều hơn một chút tao nhã (và có lẽ nhanh hơn):

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

combi sparse1 sparse2 lợi nhuận 414.0 như mong muốn.

Và nếu bạn quan tâm đến hiệu suất, hãy thử sử dụng Data.IntMap: nhanh hơn vài lần so với Data.Map tại đây.