Let Haskell functors sink in.

Question

Learn You a Haskell has an example about functors. I can read LYAH, and text, and figure out what is supposed to happen -- but I don't know enough to write something like this. I'm finding this problem often in Haskell.

instance Functor (Either a) where       fmap f (Right x) = Right (f x)       fmap f (Left x) = Left x 

However, I'm confused.. Why doesn't this comple

instance Functor (Either a) where       fmap f (Right x) = Right (x)       fmap f (Left x) = Left (f x) 

If f isn't being used in the top definition, then what else constrains x such that it can't satisfy Left

Answer 1

Here's the functor class:

class Functor f where   fmap :: (a -> b) -> f a -> f b 

Note that "f" by itself is a type constructor because it's applied to a type variable in the fmap line. Here are some examples to make this clear:

Type constructors:

IO Maybe Either String 

Types:

IO Char Maybe a Either String String 

"Maybe a" is a type with one type constructor (the "Maybe") and one type variable (the "a"). It's not something concrete yet, but it is usable in type signatures for polymorphic functions.

"Either" is a type constructor that takes two type arguments, so even after you apply one (e.g. Either String it's still a type constructor because it can take another type argument.

The point of this is: when you define a Functor instance, the type constructor f cannot change. This is because it's represented by the same variable, f, as both the argument and result of fmap. The only type that's allowed to change is the type that's applied to the f constructor.

When you write instance Functor (Either c), Either c is filled in for f everywhere in the declaration of fmap. This gives fmap the following type for this instance:

fmap :: (a -> b) -> (Either c) a -> (Either c) b 

With the definition of Either, the only useful way to get this type is by applying the Right value to the function. Remember that "Either" has two possible values with possibly different types. Here the Left value has type 'c', so you can't apply it to the function (which expects an 'a')[1], and the result also wouldn't be correct because you'd be left with Either b a, which doesn't match the class definition.

After replacing "f" with "Either c" to get the above type signature for fmap with the "Either c" instance, writing the implementation is next. There are two cases to consider, the Left and the Right. The type signature tells us that the type of the Left side, "c", can't change. We also don't have any way to change the value because we don't know what type it actually is. All we can do is leave it alone:

fmap f (Left rval) = Left rval 

For the Right side, the type signature says that we have to change from a value with type "a" to a value with type "b". The first argument is a function to do exactly that, so we use the function with the input value to get the new output. Putting the two together gives the full definition

instance Functor (Either c) where   fmap f (Right rval) = Right (f rval)   fmap f (Left lval) = Left lval 

There's a more general principle at work here which is why writing a Functor instance that adjusts the Left side is impossible, at least with the Prelude definitions. Copying some code from above:

class Functor f where   fmap :: (a -> b) -> f a -> f b  instance Functor (Either c) where ... 

Even though we have a type variable 'c' in the instance definition, we can't use it in any of the class methods because it's not mentioned in the class definition. So you can't write

leftMap :: (c -> d) -> Either c a -> Either d a leftMap mapfunc (Left x) = Left (mapfunc x) leftMap mapfunc (Right x) = Right x  instance Functor (Either c) where   --fmap :: (c -> d) -> Either c a -> Either d a   fmap = leftMap 

The result of leftMap, and thus fmap, is now (Either d) a. The (Either c) has changed to an (Either d), but this isn't allowed because there's no way to express it in the Functor class. To express this, you'd need a class with two type variables, e.g.

class BiFunctor f where   lMap :: (a -> b) -> f a c -> f b c   rMap :: (c -> d) -> f a c -> f a d   biMap :: (a -> b) -> (c -> d) -> f a c -> f b d 

In this class, since both the left and right type variables are in scope, it's possible to write methods that operate on either (or both) sides.

instance BiFunctor Either where   lMap = leftMap   rMap = rightMap  --the same as the standard fmap definition   biMap fl fr e = rMap fr (lMap fl e) 

Although in practice people usually just write "biMap" for the BiFunctor class and use "id" for the other function if a left or right mapping is necessary.

[1] More accurately, the Left value has type 'c', the function expects an 'a', but the type checker can't unify those types because the 'c' type isn't in scope in the class definition.

Answer 2

Left and Right aren't types, and Left x and Right y are of the same type. They are just constructors of Either. You may consider

Left :: c -> Either c d Right :: d -> Either c d 

You can have 2 fmap declarations because we know the Left's and the Right's are different values. It's just like

g :: Int -> Int g 1 = 2 g 2 = 4 g n = n 

Here we can't say 1 and 2 and n are different "types" just because pattern matching works.

---

The Functor class is defined such that

class Functor f where   fmap :: (a -> b) -> f a -> f b 

Note that a and b are arbitrary types. For clarity, let's rename the a in your instance to c, and the function f to func.

instance Functor (Either c) where       fmap func (Right x) = Right (x)       fmap func (Left x) = Left (func x) 

Assume your Either follows the default definition

data Either c d = Left c | Right d 

then by your definition,

fmap    func     (Right x) = Right x -- # (a -> b) ->      f a       f  b -- # f = Either c 

this forces a = b, and

fmap    func     (Left x) = Left (func x) -- # (a -> b) ->     f a       f b -- # f = Either c 

forces c = a = b. Both are not valid considering a, b and c are independent arbitrary types.