in Haskell how do you match against the type 'Either a b' ?

Question

I have an interesting problem, well at least to me and I can't seem to figure out how to resolve it, so i'm hoping you can help.

instance (Finite a, Finite b) => Finite (Either a b) where
    elems = combineLists [Left x | x <- elems] [Right x | x <-elems]
    size ??? = (size a) + (size b)

I'm working on an assignment for a class and the purpose for this particular portion is to make the size function more efficient than simply counting all the elements in elems. I've settled on summing the two types that make up the list, but i can't seem to create the signature of the size function.

From Prelude: Either a b = Left a | Right b

The first thing I tried was to match 'Either' but of course, it is a type so that doesn't work. Next I tried ((Left a) | (Right b)) but no go on that either. Nothing else seems to match the type Either a b

I was able to get size (Left a) to compile, but since it's missing the b component, I recieve the error:

Ambiguous type variable `b' in the constraint:
  `Finite b' arising from a use of `size' at <interactive>:1:0-12

which of course makes sense in the context, but I really have no clue how to match Either a b.

Anybody have any thoughts?

Answer 1

Something of type Either a b is either a Left a or a Right b, so you have two cases that can be handled separately:

size (Left x) = size x
size (Right x) = size x

The error about the ambiguous type variable is a separate issue. If you just type something like size (Left 1) into the interpreter, the system can't deduce what the "right" type of that Left 1 value would be. It could be Either Int anything and as long as it is not known what type that anything is, it cannot be checked if it is in class Finite (which is required by size).

You can avoid that problem by specifying an explicit type signature:

size (Left 1 :: Either Int String)

Answer 2

The trouble seems to be that you need a dummy argument for size, but you can't pass dummies for both types a and b in a single Either a b. Perhaps you can use the elems to get a dummy of each type:

size _ = (size . head) (elems :: [a]) + (size . head) (elems :: [b])

Answer 3

I think the core issue you are having is that you want a type that represents a datum from each of two other types at the same time. Either a b can only be one of a or b at a give time.

A simple data type that represents both an a and a b at the same time is a 2-tuple. The type signature for such a thing is (a, b), which is also the expression for creating one, and hence pattern maching one:

> :type (4,5)
(4,5) :: (Num t, Num t1) => (t, t1)
> let f (a, b) = 2*a + b
> f (4,5)
13

You should consider writing your first line with a 2-tuple, like so:

 instance (Finite a, Finite b) => Finite (a, b) where

What does this Finite (a, b) represent? What would the member function definitions be?