Haskell defining Functor instance for an alternative Either data type

Question

Going through Typeclassopedia to gain some routing working with type classes. Want to make an alternative to Either an instance of Functor, but even examining the definition of Either as an instance of Functor keeps getting me in trouble. Have this, but will not compile.

data Alt a b = Success a | Failure b deriving (Show, Eq, Ord) 

instance Functor (Alt a) where 
  fmap _ (Failure a) = Failure a
  fmap f (Success x) = Success (f x)  

    • Couldn't match expected type ‘a1’ with actual type ‘a’
      ‘a1’ is a rigid type variable bound by
        the type signature for:
          fmap :: forall a1 b. (a1 -> b) -> Alt a a1 -> Alt a b
        at Brenty_tcop.hs:25:3-6
      ‘a’ is a rigid type variable bound by
        the instance declaration
        at Brenty_tcop.hs:24:10-24
    • In the first argument of ‘f’, namely ‘x’
      In the first argument of ‘Success’, namely ‘(f x)’
      In the expression: Success (f x)
    • Relevant bindings include
        x :: a (bound at Brenty_tcop.hs:26:19)
        f :: a1 -> b (bound at Brenty_tcop.hs:26:8)
        fmap :: (a1 -> b) -> Alt a a1 -> Alt a b
          (bound at Brenty_tcop.hs:25:3)
   |
26 |   fmap f (Success x) = Success (f x) 

Answer 1

As @chepner says in the comments, your code will compile if you switch the order of the type parameters,

data Alt b a = Success a | Failure b

or alternatively switch the meaning of the Functor instance, so that it maps over Failure and leaves Success alone.

instance Functor (Alt a) where
    fmap f (Success x) = Success x
    fmap f (Failure x) = Failure (f x)

Basically, the Functor type class only knows how to map over a type's last type parameter. So we had to rejig things so that we apply the function f to an occurrence of that last type parameter.

---

Why you can only map over the rightmost parameter is a very deep and interesting question. To understand this you have to understand kinds, which are an advanced feature of Haskell's type system.

You can think of kinds as being the "next level" of types, in some sense. Types classify values; kinds classify types. So "foo" is a String, and String is a type. In Haskell "type" is pronounced *.

-- :t in ghci asks for the type of a value-level expression
ghci> :t "foo"
"foo" :: String

-- :k asks for the kind of a type-level expression
ghci> :k String
String :: *

All ordinary types - those which can have values - have a kind of *. So String :: *, Int :: *, Bool :: *, etc.

Things get interesting when you start thinking about parameterised types. Maybe is not a type by itself - you can't have values of type Maybe, but you can have Maybe Int, Maybe String, etc. So Maybe is a sort of function - it takes a type as an argument and it produces a type. (Maybe is a type constructor, to use the technical term.)

-- Maybe is a function...
ghci> :k Maybe
Maybe :: * -> *

-- and you can apply it to an argument to get a type
ghci> :k Maybe Int
Maybe Int :: *

Alt is a two-parameter type function. Type functions are curried in Haskell, just like regular value functions, so Alt has a type of * -> * -> * (which really means * -> (* -> *)).

ghci> :k Alt
Alt :: * -> * -> *

Now, Functor is a higher-order type function. It takes an argument f, which itself is a type function. Functor on its own is not a valid type class constraint, but Functor f is.

ghci> :k Functor
Functor :: (* -> *) -> Constraint

This means Maybe on its own, with a kind of * -> *, is a valid argument for the Functor type function. But Int :: * isn’t, and nor is Maybe Int :: *, and nor is Alt :: * -> * -> *. The error messages tell you about the kind mismatch:

ghci> :k Functor Int
<interactive>:1:9: error:
    • Expected kind ‘* -> *’, but ‘Int’ has kind ‘*’
    • In the first argument of ‘Functor’, namely ‘Int’
      In the type ‘Functor Int’

ghci> :k Functor Alt
<interactive>:1:9: error:
    • Expecting one more argument to ‘Alt’
      Expected kind ‘* -> *’, but ‘Alt’ has kind ‘* -> * -> *’
    • In the first argument of ‘Functor’, namely ‘Alt’
      In the type ‘Functor Alt’

The kind system is there to prevent you from forming invalid types, just like how the type system prevents you from writing invalid values. If there was no kind system, and we were allowed to write instance Functor Alt, it would produce the following (nonsensical) type for fmap:

-- `Alt a` is not a valid type, because its second argument is missing!
fmap :: (a -> b) -> Alt a -> Alt b

So we need to turn Alt :: * -> * -> * into something of kind * -> *, in order to have a valid argument for Functor. Alt is a curried type function, so if we give it a single type argument, we'll get a type function back!

ghci> :k Functor (Alt Int)
Functor (Alt Int) :: Constraint

That's why the instance declaration says instance Functor (Alt x) - it needs to give Alt an argument (and in this case the argument can be any type x as long as its kind is *). Now we have fmap :: (a -> b) -> Alt x a -> Alt x b, which is a valid type expression.

So in general, the recipe for making a Functor instance is to start by giving arguments to your type until it only has one parameter left. That's why Functor only knows how to map over the rightmost type parameter. As an exercise you can try defining a Functor class which maps over the second-to-last type parameter.

This is a big topic so hopefully I haven't gone too fast. It's OK not to understand kinds straight away - it took me several tries! Let me know in the comments if there's anything you'd like me to explain further.