views:

541

answers:

10

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

UPDATE: While not a requirement -- all answers are helpful and will be read -- I think I'd get the most if this format was followed:

Top works because ... stuff; ..., and yours -bottom- doesn't work because ... stuff; .... But, it would if ... stuff; ..., because ... stuff; ....

+6  A: 

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.

KennyTM
How come it is valid the way it is originally written then? I didn't understand this explanation, it didn't draw the connection to why my fmap doesn't work and the original did.
Evan Carroll
The more I read this answer the more confusing it is to me, `fmap f (Left x) = Left x;` `( a -> b ) -> fa fb;` Therefore, `a = b`, which isn't valid because they are *independent arbitrary types...* I think I need to move off of this answer before I go nuts.
Evan Carroll
using `f` for everything here class def., and instance def., makes this needlessly confusing.
Evan Carroll
I also don't like that you used the value constructors `Left`, and `Right` in the instance definition without deriving it or attempting to. Going straight to `fmap f (Right x) = Right (x)`, without showing the derivation of `(a -> b) -> (Either a) a -> (Either a) b` makes me feel like you're missing something major in this answer.
Evan Carroll
+1  A: 

The instance you're trying to write, let's call it fmap2 for now, has the following type:

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

If you set the LANGUAGE pragma TypeOperators, GHC also accepts the type

fmap2 :: (a -> b) -> (a `Either` c) -> (b `Either` c)

In an ideal world this also would work:

fmap2 :: (a -> b) -> (`Either` c) a -> (`Either` c) b

which would give a Functor instance for (`Either` c) but the similarity between normal operators (and their sections) and type operators breaks down at this point (unless there's a GHC option I'm missing!)

In short: your understanding of functors is okay, but you're bitten by the lack of type-level lambdas.

yatima2975
I've stared at this answer for a while, it is easily the most difficult to understand thus far. With that I voted it up, but I have no idea wtf you're talking about it -- `TypeOperators`, `type-level lambdas`... I don't see a `(\` anywhere. I don't understand how this answers the question. Why does the top work, and not the bottom. I feel like what you're talking about is some sort of Functor trickery, and I'm asking a question fit for Functors 101.
Evan Carroll
Hi Evan, I'm sorry I went over your head there, that certainly wasn't my intention! If you find an answer unhelpful, you shouldn't vote it up, by the way. That said, I'll try to expand and clarify (not right now, due to other constraints). Do you know about operator sections like `(*3)`? Or should I start at that level?
yatima2975
I know about sections, and currying, but I don't know about why you can't write a functor that applies a function to the Left side only. Or, why the Right side works given the syntax. Or, what should be the red-flag if I see syntax that has the function applied only on the Left side. I've read about 90% of LYAH and about 50% of RWH, I can read Haskell, but my attempts to write it have been pretty horrible.
Evan Carroll
+2  A: 

(Edit to try to answer the question better)

The definition of Either is:

data Either a b = Left a | Right b

So "Either" takes two type arguments. By the way, technically "Either" is not actually a type but a type constructor; it takes type arguments to create a type.

The definition of Functor is:

class Functor f where
   fmap :: (p -> q) -> f p -> f q

So in this class definition any type "f" that is an instance of Functor must take a type argument. This isn't declared; it is inferred from the "f p" and "f q"; since "f" is being given a type parameter here it must be a type that takes one.

(Note: the original definition used "a" and "b" instead of "p" and "q". I'm using different letters to keep things distinct from "Either a b" when I get to that later)

In most cases "f" is a container type like a list or a tree. So for instance you have

data Tree a = ...

instance Functor Tree where
   fmap func_a2b tree_of_a = ... --  tree of b.

However "Either" takes two type parameters, so how can we fit it into this scheme? The answer is that types can have partial application just like functions. In the same way as I can declare a function

foo x y = ...

and then say "foo 2" in order to get a new function that expects the second argument, so I can say "Either a" to get a new type that expects the second type argument.

Now look at the original instance:

instance Functor (Either a) where ....

So here "Either a" is a type constructor that expects one more argument, just like Functor expects of its instances. So the type of "fmap" for "Either a" will be

fmap :: (p -> q) -> Either a p -> Either a q

So now in the "where" clause you have to give a definition of "fmap" that has this type. The first one you quote has this type because the second type parameter is used for the "Right" constructor, and that is the one that the function is applied to. The second one won't work, because it would have the type

fmap :: (p -> q) -> Either p a -> Either q a

And that is not what the Functor class says its going to be.

Paul Johnson
The question is simply, why doesn't this compile: `fmap f (Left x) = Left (f x)` I'm not sure how this addresses the question..
Evan Carroll
+2  A: 

Hopefully, this will help...

First, though, some background:

1) Functor needs a "type constructor", a (well, not a type per se,...) type that "needs" another regular type given to it to form a "full type", just like a generic in Java/C++. So, for example, List is a Functor (it is, by the way), or Array, because (among other things) the full type isn't just List, but List<A>. So, : A Functor takes a "type constructor", an incomplete type.

2) Either is a constructor type that Haskell folks (read: Edward Kmett, and other well-math-endowed all-stars) call a bifunctor. It needs two types given to it to be complete. For example, a full use of Either is: Either Integer String which means (yeah, yeah, "duh!") it's either a (Left) Integer, or a (Right) String. So, this means Either Integer is an incomplete type that is either a Left Integer or a Right...b when you decide what that "b" is supposed to be.

Now, for the fun part!

The top stuff works because, fmap uses some type constructor, and uses it with an a -> b function to make a similar function from f a to f b - the hands-down favorite example for this in Haskell is the one for lists, AKA map :: (a -> b) -> ([a] -> [b]), where the Functor is the [ ] part. Now, using something like Either a (let's go ahead and use Either Integer from earlier), fmap's type signature looks like this:

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

and the two examples (from the Top part) show what fmap does with representative values of that Either Integer a type, in order to get an Either Integer b-typed value.

Now, yours -bottom- doesn't work, because:

  1. You have a function, f, that takes as to bs.
  2. Your Left type has to be type Integer, and stay an Integer (or type Float, and stay a Float, what ever type is the left one of the two types of the Either type you're using).
  3. Your Right type has to be of whatever type that the function takes ("a"), and go to the type that the function makes ("b").

It has to do this (but your stuff doesn't - that's why it doesn't work), because that's the type that fmap needs to have. Specifically, you have these equations:

fmap f (Right x) = Right (x)  
fmap f (Left x) = Left (f x)

Your equations give fmap the types:

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

which not only doesn't fit what fmap wants, but it isn't even consistent with each other!

I'm sorry I wrote half a book to wade through, but I hope that gives some insight to you.

BMeph
I'm sort of confused, how come you say my equations aren't even consistent with each other, and @sciv said they work, just not for the signature of `fmap`?
Evan Carroll
Sorry - "given the current definition of fmap", your definitions do not match, and are inconsistent with each other. That is, working from the conventional definition, and trying to unify the type of the Functor as `Either e` (where by `e` I'm just using a variable name that hasn't come up yet), your equations will force unification to occur in a way that is inconsistent with how fmap is used, and with how it is meant to be defined.Basically, what you want (an `fmap` that works on the `Left` values instead of the `Right` ones) would need a different kind of `Either`...I'll make a new reply.
BMeph
Shoot, never mind; check out Kali Mist's response. That's what I would have written. A Functor has to have that "give it a type and it makes the name for a 'new' type"-kind of structure that other responders have mentioned. That is, A Functor is a type-level unary function. I'd just say "look at the types involved, and remember that you're explaining how the function works to a computer."
BMeph
+5  A: 

Ok so here's another very simple try at this.

You ask why this doesn't compile:

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

So let's try to simplify the problem by trying to define the same function without putting it as part of a class instance declaration:

That gives us

foo f (Right x) = Right (x)
foo f (Left x) = Left (f x)

Which indeed does compile. ghci tells us the type signature:

*Main> :t foo
foo :: (t1 -> a) -> Either t1 t -> Either a t

We'll rename some of the variables to get something more uniform looking:

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

That makes perfect sense. It takes a function and applies it to the Left of an Either.

But what's the signature for fmap?

*Main> :t fmap
fmap :: (Functor f) => (a -> b) -> f a -> f b

So let's substitute Either c for f in the fmap signature (I renamed Either a to Either c to keep our two different as from getting mixed up):

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

Do you see the problem? Your function is perfectly valid -- it just has a different type than what fmap for Either a must necessarily have.

This is a sort of beautiful thing about types. Given the signature for fmap, there is really only one meaningful implementation for fmap on Either a.

Sometimes, when we're lucky and careful, we can end up in similar situations -- given a type signature, the function almost writes itself.

Edit: trying to answer the questions below.

1) There's no "composition of two functions" going on. To get the type signature for fmap over Either a just go through the fmap function signature, and every place you see f, replace it with Either a. We would call that a "specialization" of the type signature of fmap. Which is to say, it is strictly less general than the normal type of fmap -- anyplace that requires a function of the more specialized type, you can pass in something of the general type with no problems.

2) Your function for mapping over the left side (which I named "foo" in the above examples) is just fine. It works fine, it does what you want. You just can't name it fmap and use it in a Functor instance. Personally, I'd name it something like onLeft or mapLeft.

All the following can be ignored/is for information, but not a suggestion for future reading in the near future/actual use:

If one wants to get very technical, because you can map over both the left and the right side (although you can only declare Functor for the latter), Either is not only a Functor, but a Bifunctor. This is provided in, e.g., ekmett's Category-Extras library ( see http://hackage.haskell.org/packages/archive/category-extras/0.44.4/doc/html/Control-Bifunctor.html).

There's lots of cool stuff involving calculating with programs, and "origami programming" that uses bifunctors more rigorously. You can read about it here: http://lambda-the-ultimate.org/node/1360. But, you probably don't want to, at least until you're much more familiar with Haskell. It is computer-sciency, mathy, researchy, and very cool, but not necessary at all to understand idiomatic Haskell programming.

sclv
Can you show how the composition of those two functions produced that signature? And, can you please speak of how you would go about mapping over the left side too. This answer is great!
Evan Carroll
To be more specific, you say in your post, "Which indeed does compile. ghci tells us the type signature:" How does ghci generate the type signature for this.. I think I misapplied the term *compose*
Evan Carroll
I'd like to also say, that unique amongst all of the responses, this is the first one that says my signature is valid just not for the type *fmap*, which actually tells me something of my problem that I wasn't 100% sure of. This also makes me wonder why the `Right` side receives preferential treatment in the prelude.
Evan Carroll
And, another question, you say `foo :: (a -> b) -> Either a c -> Either b c`, and in order to get what the right signature is you substitute `f` as `Either c` in the true fmap signature `(a -> b) -> f a -> f b`. You said my instance definition is also ok, but not for a fmap? If a Functor requires kind '* -> *' what Type constructor will yield my `foo :: (a -> b) -> Either a c -> Either b c`? I'm guessing (`Either c`) ?
Evan Carroll
There is no type constructor to the signature of `fmap` that will yield your `foo`. This is because `f a` only lets you vary over the *last* parameter of the type constructor. If we had type level lambdas (and there's good reasons why we don't), you could write something like `instance Functor (L x -> Either x a) where...` (where L is like \ but at the type level). Mathematically, Either is indeed a functor in two ways. In Haskell, however, it is not.
sclv
One last note -- we *can* write `newtype Flip t a b = Flip (t b a)` and `instance Functor (Flip Either a) where fmap f (Flip e) = Flip (foo f e)` if we *really* want to capture that mathematical fact.
sclv
+3  A: 

While I will eventually cleave to your format, I'm going to start with something in a slightly different format, as I think it will make my explanation clearer.

Let's consider a different datatype

data Choice a = Default Integer | Chosen a

-- This corresponds to your top, working, instance.
instance Functor Choice where
  fmap f (Default i) = Default i
  fmap f (Chosen  a) = Chosen  (f a)

It should be clear why this instance works. However, what about the following:

-- Broken!
instance Functor Choice where
  fmap f (Default i) = Default (f i)
  fmap f (Chosen  a) = Chosen  a

You should be able to see why this doesn't work. The type of fmap is Functor f => (a -> b) -> f a -> f b; in this context, it's (a -> b) -> Choice a -> Choice b. Thus, the f argument has the type a -> b. However, in the second (failed) instance declaration, you write f i. We know, because of the datatype declaration, that i must be an Integer, so we can't apply f to it. Similarly, since a has type a, Chosen a will have type Chosen a, not type Chosen b. Thus, the Functor instance on the bottom can't work.

Well, your top instance for Either works because, like in the Choice example, it obeys the types. Let's look at it, with a few renamings:

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

This instance declaration doesn't declare an instance of Functor for Either—it can't. Something which is an instance of Functor must take one type parameter. Thus, Int can't be a functor, since Int takes no type parameters, but [] and Maybe can be, since [a] and Maybe a are complete types. Either, however, takes two type parameters: Either a b. Thus, what this instance does is declare that Either c is a functor for any possible c. That c is fixed for the duration of the instance declaration. So let's go through and add types (this is not legal syntax!):

instance Functor (Either c) where
  fmap :: forall a b. (a -> b) -> (Either c) a -> (Either c) b
  fmap f (Left  (c :: c)) = Left  c
  fmap f (Right (a :: a)) = Right (f a :: b)

Since f has type a -> b, but c's type is fixed at c, we can't possibly write Left (f c); and even if we could, we want the c to be left alone, so that we can return an (Either c) b. Similarly, we must apply f to a in order to get something of type b.

This is also why your bottom instance doesn't work: you have a function which needs to work for any type being applied only to the fixed type c, and you leave the type you need to transform alone. Let's look at it, again with type signatures added:

instance Functor (Either c) where  
  fmap :: forall a b. (a -> b) -> (Either c) a -> (Either c) b
  fmap f (Left  (c :: c)) = Left  (f c)
  fmap f (Right (a :: a)) = Right a

Here, your first part of the function definition attempts to apply a function f :: a -> b to something of the fixed type c, which cannot work, so this already fails. But let's look at what type this generates. In this case, we'd expect that (somehow) f c would have the type b, and a would have the type a. In that case, we're returning a value of type Either b a, which is still not allowed.

Basically, the problem stems from this. First, note that f is the same in between the two function definition clauses, so it can't change between lines. Second, note that we are fixing c, and declaring an instance for that c. This is true for any c, but we only look at one at a time. Finally, because of this, Left's argument is not parametrized by the type that f expects; it's guaranteed to have some fixed type c. This means that (a) you can't apply f to it, and (b) you must apply it to Right's argument, since otherwise you won't change the type you're expected to change.

Antal S-Z
I don't know what `forall` means, why the syntax is illegal (or what you're trying to demonstrate over legal syntax), and I'm *not able to see why [it] doesn't work*
Evan Carroll
The `forall` doesn't actually say anything. Consider, for instance the type of `id`, namely `a -> a`. There's an *implicit* `forall a.` in front of the type signature, which says "this is true for any possible `a`". With the right GHC extensions, you can put it in explicitly, but in this context, it doesn't add you anything. I was hoping it might be clearer, but apparently I was mistaken :)
Antal S-Z
As for the illegal syntax: you understand type signatures (with `::`), yes? Well, the way in which I specified a type for `fmap` and a type for the function arguments isn't actually legal syntax, but hopefully helps make the types of the variables explicit. And as for what you aren't getting: I'll try to take another shot at it, but I'll be honest, I'm not entirely sure what it is you don't get. Is there some particular part of my answer that confuses you, or seems to take a logical leap? If there is, I can zero in on that.
Antal S-Z
I actually think @sclv has the best seed for a good answer. I'm not sure he has enough -- nothing has clicked, no real strong eureka -- maybe the way of haskell is just to drag through it. But, i follow 100% of what sclv had to say. There were some valid questions or follow-ups I requested. His footnote I even found especially helpful, Control.Bifunctor actually has my Functor written as `second`, I actually think the root of my problem was just thinking in the box I could write a functor to do what I wanted, and that to do that I had to define an fmap. I just don't know if I'm getting it yet.
Evan Carroll
That's fair; I'm glad you're getting a handle on this. I will provide one other resource: [the Typeclassopedia](http://www.haskell.org/sitewiki/images/8/85/TMR-Issue13.pdf) (it's the second article). I'm not sure if you'll find this helpful or not, but it covers all the "algebraic" type classes (`Functor`, `Monad`, `Applicative`, …). It's what helped me get my intuition for functors (I'm still working on some of the others).
Antal S-Z
+1  A: 

Ehm... How about a few words about "kinds" ?..
That may simplify understanding, I guess.
Remember what is currying. I.e. in ghci:

Prelude> let f x y z = x + y * z
f :: (Num a) => a -> a -> a -> a
Prelude> :t f 1
f 1 :: (Num t) => t -> t -> t
Prelude> :t f 1 2
f 1 2 :: (Num t) => t -> t
Prelude> :t f 1 2 3
f 1 2 3 :: (Num t) => t

The same things you have with types. When you say Either kind of that type is * -> * -> * (i.e. it takes two types and produces type) and when you say Either a kind is * -> * and for Either a b it's * (btw Monad a and Functor a requires a to be of kind * -> *, as I remember). So when you say type Either a that means type that is still incomplete (requires some "argument" to be bound), so fmap :: (a -> b) -> f a -> f b becomes fmap :: (a -> b) -> (Either c) a -> (Either c) b when f substituted by Either c.

ony
+10  A: 

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.

John
Nice. Very nice. You should try to get some variation of this explanation put into LYAH itself. Wish I could give more than +1.
JUST MY correct OPINION
This is a damn good explanation. I'd take it one step closer, and rename the function variable in the instance declaration as something other than `f` to help differentiate it from the `f` in the class declaration -- I think they're different -- maybe, instance_func. I think this answer takes the lead.
Evan Carroll
I'm going to update the status of my confusion: I think it was partly because I thought Functor was the only type class that can iterate over something, and that all things that iterated over something had to be an `fmap`, and I think I was confusing the `f` in the class definition with the `f` the instance definition. Which I'm now 99.9% sure is totally different, thanks again. This is a great example.
Evan Carroll
I've edited my example to rename the "f" in the (incorrect) instance definition to something else. It's unfortunate that both the type variable and function binding typically use `f` with Functor, because they are unrelated.
John
I've read your example many times now, this is the best explanation of Functors I've found yet -- I think I've chosen! Congrats, and welcome to Stack Overflow.... Now, leave and go write a book -- I'll preorder. ;)
Evan Carroll
Could you show the `Left`, in the same way you show `Right`, to derive `fmap f (Left x) = Left x`, or somehow show better what `fmap f (Left x) = Left x` means.
Evan Carroll
I also think the top has an error, you have `map :: (a -> b) -> f a -> f c`, i think it should be ` fmap :: (a -> b) -> f a -> f b`
Evan Carroll
Thanks, glad it helped. I can't find the 'map' error you mention, maybe somebody else fixed it?
John
Very good answer. The error I can see is in the ver first piece of code, where you give the definition of the functor class. At this time of writing, it says fmap :: (a -> b) -> f a -> f c, (so not map, but fmap) where it should say fmap :: (a -> b) -> f a -> f b. By the way, how can you markup code in comments?
Boris
@Boris, thanks for catching this; fixed now. Comments use the same markup syntax as regular posts, Markdown. I don't think indenting 4 spaces works, but you can put code snippets in \`backticks\`. There's a short introduction at the StackOverflow [tutorial](http://stackoverflow.com/editing-help).
John
A: 

Top works because fmap::(b -> c) -> Either a b -> Either a c and yours -bottom- doesn't work because that would require fmap::(a -> c) -> Either a b -> Either a c. But, it would work if you changed Either to

data Either' a b = Left' b | Right' a deriving (Eq, Show)

instance Functor (Either' a) where  
    fmap f (Right' x) = Right' (x)  
    fmap f (Left' x) = Left' (f x)
supertux
+1  A: 

Belive it or not, this isn't magic. It all has to do with the type Either a b not being the same type as Either b a. Here is the definition of Either from Prelude

data  Either a b  =  Left a | Right b

... Notice How the type variable a comes first, then b, and also notice that we only include a in the declaration of the Either Functor:

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

Now lets look at the definition of the Maybe Functor

instance Functor Maybe where
    fmap = map

Here there is no type variable, Although Maybe takes one type parameter (like Maybe Int). What I am trying to get to is that types aren't functors, type constructors are functors (functors have kind *->*).

So let f :: b -> c, in the version of the Either Functor that works, the x from (Left x) is of type a, which is fine since it's (Either a) that is a functor, the x in (Right x) is of Type b so (Right x) is of type ((Either a) b), and (Right (f x)) is of type ((Either a) c), therefore fmap is of type (b->c) -> ((Either a) b) -> ((Either a) c), as required.

In your version that failed, we have that x in (Right (x)) is not of type a, but of type b, So (Right (x)) is not of type ((Either a) c) which doesn't fit with the type of fmap.

so to sum it up: the fmap that works comes out : (b -> c) -> (Either a) b -> (Either a) c, but the one that doesn't work comes out: (b -> c) -> (Either b) a -> (Either c) a and thats not the right type for fmap.

HaskellElephant
I liked this definition too. It brings to the table that `Either a b` is not the same as `Either b a` which is something that I didn't know prior to this question, the rest of it i'm not sure I get. I suppose that stems from variable naming though...
Evan Carroll