[Haskell-cafe] Question concerning datatype "Either"

[Loup Vaillant]

2008/7/4 phy51km4n <phy51km4n at yahoo.de>:
>
> There is a exercise using datatype "Either" I'm a bit confused about...
>
> The following datatypes are given:
>
> data Either a b = Left  a
>                | Right b
>
> data Tuple a b c d = One   a
>                   | Two   a b
>                   | Three a b c
>                   | Four  a b c d
>
> Now the exercise:
>
> "Based on our definition of Tuple, write a function which takes a Tuple and
> returns either the value
> (if it's a one-tuple), a Haskell-pair (i.e., ('a',5)) if it's a two-tuple, a
> Haskell-triple
> if it's a three-tuple or a Haskell-quadruple if it's a four-tuple. You will
> need to
> use the Either type to represent this."
>
> Why does that not work? :
>
> fromTuple (One   a)       =  a
> fromTuple (Two   a b)     = (a, b)
> fromTuple (Three a b c)   = (a, b, c)
> fromTuple (Four  a b c d) = (a, b, c, d)

The first  line tells: fromTuple :: Tuple a b c d -> a
The second line tells: fromTuple :: Tuple a b c d -> (a, b)
The third  line tells:  fromTuple :: Tuple a b c d -> (a, b, c)
The fourth line tells:  fromTuple :: Tuple a b c d -> (a, b, c, d)

There is no way you can unify the return types of these four lines
(Well, the compiler must have told you something similar). That was
the obvious part.

> Why is this correct? :
>
> fromTuple (One   a )      = Left  (Left   a)
> fromTuple (Two   a b )    = Left  (Right (a,b))
> fromTuple (Three a b c )  = Right (Left  (a,b,c))
> fromTuple (Four  a b c d) = Right (Right (a,b,c,d))
>
> Why does this combination of Rights and Lefts work and how does it work??

OK, first, let's simplify things a bit:

data Stuple a b = Sone a | Stwo (a, b)

fromStuple :: Stuple a b -> Either a (a, b)
fromStuple (Sone a) = Left a
fromStuple (Stwo (a, b)) = Right (a, b)

According to the definition of Either, I can perfectly retrun
different types for left and right. (That was the whole point of the
Either type.) In your more complicated case, you can see you are using
four combination of Left and Rights. The type of your function is
(tell me if your compiler says otherwise):

Tuple a b c d -> Either (Either a (a, b)) (Either (a, b, c) (a, b, c, d))

Ouch. Either is parametrized by two types: the one used in Left, and
the one used in Right. If your are using Either types as left an
right, it is possible to parametrize each of them by two types
totalazing four types. Let me rewrite the return type above so you can
read its tree structure more easily:

Either
   (Either
      a
      (a, b))
   (Either
      (a, b, c)
      (a, b, c, d))

Here, this should be obvious: while an Either type can hold two types,
this nested one can hold four types.

Hope this helps.
Loup