Haskell - Funktory

Question

Próbuję zrozumieć, jak działają Funktory, więc przeczytać o tym tutaj: http://learnyouahaskell.com/making-our-own-types-and-typeclasses#the-functor-typeclass

Mam funkcję, która pobiera mapy i oblicza sumę wartości (co jest lista).

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

I naprawdę nie rozumiem, jak fmap pracował tak czytam o tym i próbowali stworzyć własną wersję. Nie mogę tego przetestować, ponieważ Map jest już zdefiniowana w bibliotece Haskell.

Czy to prawda?

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

Answer 1

Twój przykład jest moralnie na dobrej drodze, ale jest w nim kilka błędów. Najbardziej oczywiste jest to, że nie można dopasować wzorca na fromList ..., ponieważ fromList nie jest konstruktorem. Faktyczne konstruktory nie są eksportowane przez moduł Data.Map, więc nie możemy w ogóle dopasować wzorca - ma to na celu uniemożliwienie dostępu do wewnętrznej reprezentacji drzewa używanej w tym module i prawdopodobnie złamanie niektórych niezmienników.

Lepszą instancją może być np. (Ograniczenie Ord k jest wymagane przez Map, jak @gallais wspomina)

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

to zasadniczo zmienia całą mapę do listy stowarzyszenia wykonane z par klucz-wartość, a następnie zmienia każdą wartość stosowania f, a następnie odbudowuje Mapa plecy. Bardziej zwięźle, może być zapisana jako

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

Należy pamiętać, że to nie jest strasznie wydajny - rzeczywiste wystąpienie w module Mapa nie musi przechodzić przez liście pośredniej.

Należy pamiętać, że nie można zdefiniować własnej instancji, ponieważ moduł Map już ją udostępnia. Jeśli naprawdę chcą eksperymentować z nim, można zadeklarować 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