[Haskell-cafe] A Question of Restriction

Wouter Swierstra wss at Cs.Nott.AC.UK
Tue Jul 28 03:54:02 EDT 2009

> Would you be so kind as to elaborate?

Sure. I'll just sketch how to deal the example in your e-mail. If you  
want to use recursive data types (like Lists or Trees), you'll need to  
use the Expr data type from the paper.

Instead of defining:

 > data Foo = One | Two | Three | Four

Define the following data types:

 > data One = One
 > data Two = Two
 > data Three = Three
 > data Four = Four

You can define the following data type to assemble the pieces:

 > infixr 6 :+:
 > data (a :+: b) = Inl a | Inr b

So, for example you could define:

 > type Odd = One :+: Three
 > type Even = Two :+: Four
 > type Foo = One :+: Two :+: Three :+: Four

To define functions modularly, it's a good idea to use Haskell's  
clasess to do some of the boring work for you. Here's another example:

 > class ToNumber a where
 >   toNumber :: a -> Int
 > instance ToNumber One where
 >    toNumber One = 1

(and similar instances for Two, Three, and Four)

The key instance, however, is the following:

 > instance (ToNumber a, ToNumber b) => ToNumber (a :+: b) where
 >    toNumber (Inl a) = toNumber a
 >    toNumber (Inr b) = toNumber b

This instance explains how to build instances for Odd, Even, and Foo  
from the instances for One, Two, Three, and Four. An example ghci  
sessions might look like:

*Main> let x = Inl One :: Odd
*Main> toNumber x
*Main> let y = Inr (Inr (Inl Three) :: Foo
*Main> toNumber y

Of course, writing all these injections (Inr (Inr (Inl ...))) gets  
dull quite quickly. The (<) class in the paper explains how to avoid  

I hope this gives you a better idea of how you might go about solving  
your problem. All the best,


More information about the Haskell-Cafe mailing list