Supponiamo 2 mappeÈ brutto da usare per elencare?
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)]
Come si fa a definire una funzione elegante
combi :: M.Map Int Float -> M.Map Int Float -> Float
tale che sparse1 combi sparse2 restituisce 414,0 (= 5 * 19 + 11 * 29), perché 12 e 102 sono gli unici chiavi comuni delle due mappe? V'è un elegante (semplice ed efficiente) funzione con liste in quanto tali sarebbero rigorosamente ordinato:
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
Ma è
combi m1 m2 = combiList (M.toList m1) (M.toList m2)
una buona idea sapendo le liste non sono più utilizzati nel resto del codice ? E se no, come scriverebbe efficacemente combi senza listare?
Sono d'accordo che è più elegante, ma è più veloce? Non credo che in GHC, la generazione di una mappa da Map.intersectionWith e il consumo di una mappa da Map.fold siano fusi, e quindi questo codice potrebbe essere più lento se ci sono molte chiavi comuni. –
In questo caso, non possiamo ottenere prestazioni veramente buone da 'Data.Map'. 'Fold' e' intersectionWith' sono entrambi pigri e creeranno dei thunk aggiuntivi. – tibbe