1

I believe that it could be if we consider the values in the map as the values to consider in the functor and the keys as part of the context (I am pulling this language from Typeclassopedia ) but I am not sure if these considerations mean that it is not, generally, a functor.

griotspeak
  • 13,022
  • 13
  • 43
  • 54

3 Answers3

8

Yup, you have an example of such in the containers package called Data.Map.Map. It's an instance of Functor.

You can also think of a map as a function from keys to Maybe values

newtype Map k v = Map { lookup :: k -> Maybe v }

Since (->) k is a Functor and Maybe is a Functor and compositions of Functors are Functors then Map is also a Functor.

J. Abrahamson
  • 72,246
  • 9
  • 135
  • 180
2

Yes, a dictionary should be defined by something like

data Dict k v = ...

and then our instance for Functor would look like

instance ConstraintsOnKey k => Functor (Dict k) where
  ...

Notice that we partially applied the Dict type constructor so that we fmap over values in the dictionary. In particular

fmap :: (a -> b) -> Dict k a -> Dict k b

so fmap can never modify the "structure" of our dictionary, what keys are in the dictionary. This is the case with the most common map in Haskell, Data.Map.

daniel gratzer
  • 52,833
  • 11
  • 94
  • 134
  • when you take `k` to be part of the "structure", yes - and the OP says so as well, with their *"if we consider the values in the map as the values to consider in the functor and the keys as part of the context"* -- but then their question is, it seems, is it so ***"generally"***, too (whatever that can mean)? – Will Ness Jun 28 '14 at 10:08
2

Yes, as long as the keys are independent of the values (as is the case for a general map/dictionary type).

If however you have a map/dictionary like type with an invariant that the key depends on the mapped to value, this is no more true. An example would be when the mapped to type is a record (say of type Person) and the keys are part of it (say of type SocialSecurityCode). If such an invariant is part of the structure, than it cannot be a functor.

You can easily verify if your functor instance is valid by checking the functor laws:

fmap id == id
fmap (g . h) == (fmap g) . (fmap h)
Will Ness
  • 70,110
  • 9
  • 98
  • 181
Analog File
  • 5,280
  • 20
  • 23
  • the problem in your example is not with the literally understood "shape", but that [Functor doesn't allow constraints on the type parameters](http://stackoverflow.com/questions/17157579/functor-instance-for-a-gadt-with-type-constraint#comment24838032_17157579) - because there must be a way to produce *keys* from your *records*, which is a type constraint on those records. A Functor must be able to carry *any* type of value. – Will Ness Jun 28 '14 at 09:50