How do you match against the type “Either a b”?

0 votes
asked Feb 22, 2010 by fry

The purpose for this particular portion of code 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.

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)

From Prelude, we know that 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 receive 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?

3 Answers

0 votes
answered Jan 22, 2010 by nefrubyr

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])
0 votes
answered Jan 22, 2010 by mtnviewmark

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)

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?

0 votes
answered Feb 22, 2010 by sth

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)
Welcome to Q&A, where you can ask questions and receive answers from other members of the community.
Website Online Counter