Search code examples
haskellfunctor

Couldn't match type `a` with `a1`

I am doing the exercise in the Haskell Programming from First Principles, Chapter 16. The question is to ask us to write Functor definition for the datatype:

{-# LANGUAGE FlexibleInstances #-}
newtype Flip f a b = Flip (f b a) deriving (Eq, Show)
newtype K a b = K a
instance Functor (Flip K a) where
  fmap = undefined

Here is my try:

{-# LANGUAGE FlexibleInstances #-}
newtype Flip f a b =
  Flip (f b a)
  deriving (Eq, Show)

newtype K a b =
  K a

-- instance Functor (K a) where
-- fmap _ (K a) = K a

instance Functor (Flip K a) where
  fmap _ (Flip (K a)) = Flip (K a)

but it does not compile:

chapEx2.hs:17:25: 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) -> Flip K a a1 -> Flip K a b
        at chapEx2.hs:17:3-6
      ‘b’ is a rigid type variable bound by
        the type signature for:
          fmap :: forall a1 b. (a1 -> b) -> Flip K a a1 -> Flip K a b
        at chapEx2.hs:17:3-6
      Expected type: Flip K a b
        Actual type: Flip K a a1
    • In the expression: Flip (K a)
      In an equation for ‘fmap’: fmap f (Flip (K a)) = Flip (K a)
      In the instance declaration for ‘Functor (Flip K a)’
    • Relevant bindings include
        a :: a1 (bound at chapEx2.hs:17:19)
        f :: a1 -> b (bound at chapEx2.hs:17:8)
        fmap :: (a1 -> b) -> Flip K a a1 -> Flip K a b
          (bound at chapEx2.hs:17:3)
   |
17 |   fmap f (Flip (K a)) = Flip (K a)
   |                         ^^^^^^^^^^

Can someone explain the error message? I just feel confused about the error message:

  1. Why does compiler deduce the Actual type to be Flip K a a1 rather than Flip K a b?
  2. Why the compiler bother to match the third parameter of K? The type K's definition only has one a but no b, the b only occurs in the left of dataclass declaration (left side of the = sign) but not the typeclass declaration(right side of the = sign) of newtype K a b = K a.
  3. Why the Flip (K a) cannot be changed to Flip x?
  4. I found fmap f (Flip (K a)) = Flip (K (f a)) compiles, what is the difference?
Solution

  • Question 1

    You've made a mistake. The Flip means that you need to map over the first parameter of K:

    instance Functor (Flip K a) where
  fmap f (Flip (K a)) = Flip (K (f a))

    Question 2

    There are good reasons for this. One of them is that it can be extremely useful (to maintain program invariants or to guide instance resolution) to give a type a phantom parameter. Those techniques would be worthless if the compiler just ignored them. (Note: you can ignore them when you need to, and Data.Coerce gives some advanced tools for doing so. You're probably not ready for coercions yet).

    Another reason is that it would be considerably harder to figure out what types were equal to what other types, since you'd have to look at details of each. There are probably more reasons.

    An aside

    FlexibleInstances seems rather awkward and limiting here. Here's how I'd do it:

    -- A functor in the second to last type argument
class Functor2 p where
  fmap2 :: (a -> a') -> p a b -> p a' b

instance Functor2 K where
  fmap2 = -- you fill in the blank

instance Functor2 p => Functor (Flip p b) where
  fmap = -- you fill in the blank