Map data structure implementation

Question

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

(\(k, v) -> (k, v)) doesn't do anything. It seems you forgot to use f there. — duplode
– duplode, Commented Apr 19, 2018 at 19:26
Well the compiler gives an error. Usually that is a good starting point to debug. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Apr 19, 2018 at 19:26

willeM_ Van Onsem · Accepted Answer · 2018-04-19 19:33:35Z

3

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.

answered Apr 19, 2018 at 19:33

willeM_ Van Onsem

482k33 gold badges483 silver badges624 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

barnabas markus Over a year ago

is it possible to apply the function on the key?

willeM_ Van Onsem Over a year ago

@barnabasmarkus: no, since Functor f, expects an f with one type parameter, and here that is the value. You can of course redesign it, and define a Map v k, such that you can fmap on the values, but not the way the Map is currently defined.

barnabas markus Over a year ago

thanks a lot! that was my original question, but somehow I have made a mistake when I posted here!

Collectives™ on Stack Overflow

Map data structure implementation

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related