Haskell - Funtori

Question

sto cercando di capire come funzionano Funtori, così ho letto su di esso qui: http://learnyouahaskell.com/making-our-own-types-and-typeclasses#the-functor-typeclass

ho una funzione che prende una mappa e calcola la somma dei valori (che è una lista).

reduce :: Map String [Int] -> Map String Int 
reduce = fmap sum 

non ho davvero capito come il fmap lavorato così ho letto su di esso e ha cercato di fare la mia versione. non posso davvero provarlo perché la mappa è già definita nella libreria Haskell.

Quindi è giusto?

instance Functor (Map k) where 
    fmap f fromList[] = [] 
    fmap f fromList[(k, v): xs] = (f v) fmap xs 

Answer 1

Il tuo esempio è moralmente sulla buona strada, ma ci sono alcuni errori in esso. Il più evidente è che non è possibile eseguire lo schema di corrispondenza su fromList ... poiché fromList non è un costruttore. I costruttori effettivi non vengono esportati dal modulo Data.Map in modo da non poter eseguire lo schema di corrispondenza - questo è per garantire che non è possibile accedere alla rappresentazione ad albero interna utilizzata in quel modulo ed eventualmente rompere alcuni invarianti.

Un'istanza migliore potrebbe essere ad es. (Il vincolo Ord k è richiesto da Map, come @gallais menzioni)

instance Ord k => Functor (Map k) where 
    fmap f m = fromList (map modify (toList m)) 
     where modify (k,v) = (k, fv) 

questo risulta sostanzialmente l'intera mappa in una lista un'associazione fatta di coppie di valori-chiave, poi cambia ogni valore applicando f, e quindi ricostruisce mappa indietro. Più sinteticamente, può essere scritta come

instance Ord k => Functor (Map k) where 
    fmap f = fromList . map (\(k,v) -> (k,f v)) . toList 

Tenete a mente che questo non è molto efficiente - l'istanza effettiva nel modulo Mappa non deve passare attraverso una lista intermedia.

Infine, si noti che non è possibile definire la propria istanza poiché il modulo Mappa ne fornisce già uno. Se davvero si vuole sperimentare con esso, è possibile dichiarare una newtype:

newtype MyMap k v = MyMap { unMyMap :: Map k v } 

instance Functor (MyMap k) where 
    fmap f = MyMap . fromList . map (\(k,v) -> (k,f v)) . toList . unMyMap