Haskell - Functors

Question

I'm trying to understand how Functors work, so I read about it here: http://learnyouahaskell.com/making-our-own-types-and-typeclasses#the-functor-typeclass

I have a function that takes a map and calculates the sum of the values (which is a list).

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

I didn't really understand how the fmap worked so I read about it and tried to make my own version. i can't really test it because Map is already defined in the Haskell library.

So is this right?

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

Answer 1

Your example is morally on the right track, but there are a few mistakes in it. The most evident is that you can not pattern match on fromList ... since fromList is not a constructor. The actual constructors are not exported by the Data.Map module so we can not pattern match at all -- this is to ensure that you can not access the internal tree representation used in that module and possibly break some invariant.

A better instance could be e.g. (the constraint Ord k is required by Map, as @gallais mentions)

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

this basically turns the whole map into an association list made of key-value pairs, then changes every value applying f, and then rebuilds the Map back. More succinctly, it can be written as

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

Keep in mind that this is not terribly efficient -- the actual instance in the Map module does not have to pass through an intermediate list.

Finally, note that you can not define your own instance since the Map module already provides one for you. If you really want to experiment with it, you can declare a 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