Search code examples
haskellfunctor

Map data structure implementation

What's the problem w this Functor instance?

data Map k v = Map [(k, v)] deriving (Show, Eq)

instance Functor (Map a) where
  fmap _ (Map []) = Map []
  fmap f (Map xs) = Map xs'
    where xs' = map (\(k, v) -> (f k, v)) xs
Solution

  • If we compile this, we get the error:

    <interactive>:6:21: error:
    • Couldn't match type ‘a1’ with ‘b’
      ‘a1’ is a rigid type variable bound by
        the type signature for:
          fmap :: forall a1 b. (a1 -> b) -> Map a a1 -> Map a b
        at <interactive>:5:3
      ‘b’ is a rigid type variable bound by
        the type signature for:
          fmap :: forall a1 b. (a1 -> b) -> Map a a1 -> Map a b
        at <interactive>:5:3
      Expected type: Map a b
        Actual type: Map a a1
    • In the expression: Map xs'
      In an equation for ‘fmap’:
          fmap f (Map xs)
            = Map xs'
            where
                xs' = map (\ (k, v) -> (k, v)) xs
      In the instance declaration for ‘Functor (Map a)’
    • Relevant bindings include
        xs' :: [(a, a1)] (bound at <interactive>:7:11)
        xs :: [(a, a1)] (bound at <interactive>:6:15)
        f :: a1 -> b (bound at <interactive>:6:8)
        fmap :: (a1 -> b) -> Map a a1 -> Map a b
          (bound at <interactive>:5:3)

    The error actually is a good starting point: it says that your fmap should have signature:

    fmap :: forall a1 b. (a1 -> b) -> Map a a1 -> Map a b

    but apparently your output type is Map a a1, so you did not met these contracts. If we further investigate, we see that map (\(k, v) -> (k, v)) xs actually does not do much (except repacking the data in a new tuple). The output tuple should have type (a, b) instead of (a, a1) (a1 being the original type of the values in the Map).

    We thus should apply f on the value, like:

    instance Functor (Map a) where
  fmap _ (Map []) = Map []
  fmap f (Map xs) = Map xs'
    where xs' = map (\(k, v) -> (k, f v)) xs

    or in a more clean way:

    instance Functor (Map a) where
  fmap f (Map xs) = Map (fmap (fmap f) xs)

    Note that you do not need to implement two separate cases here (one for an empty and one for a non-empty list), since a map (or fmap) on an empty list is an empty list.