क्या यह सूची में बुरा है?

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) 

एक अच्छा जानते हुए भी सूचियों नहीं के बाकी हिस्सों में अधिक इस्तेमाल कर रहे हैं विचार है कोड? और यदि नहीं, तो आप बिना लिस्ट के कम्बी को कुशलतापूर्वक कैसे लिखेंगे?

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 से कई गुना तेज होना चाहिए।