[Haskell-cafe] A Question of Restriction

wren ng thornton wren at freegeek.org
Tue Jul 28 03:56:06 EDT 2009

Brian Troutwine wrote:
> Hello Wouter.
> I've had a go at the paper linked and perused other references found
> with Google. Unfortunately, such sophisticated use of the type system
> is pretty far out of my normal problem domain and I can't see how to
> apply the techniques presented to my motivating example. Would you be
> so kind as to elaborate?

     data Foo = One | Two | Three | Four
     data Odd = One | Three
     data Even = Two | Four


     data Fix f = Fix { unFix :: f (Fix f) }
     data (:+:) f g x = Inl (f x) | Inr (g x)

     data One   r = One
     data Two   r = Two
     data Three r = Three
     data Four  r = Four

     instance Functor One   where fmap _ One   = One
     instance Functor Two   where fmap _ Two   = Two
     instance Functor Three where fmap _ Three = Three
     instance Functor Four  where fmap _ Four  = Four

     type Foo  = Fix (One :+: Two :+: Three :+: Four)
     type Odd  = Fix (One :+: Three)
     type Even = Fix (Two :+: Four)

If your original types were actually recursive, then the unfixed 
functors should use their r parameter in place of the recursive call, e.g.

     data List a = Nil | Cons a (List a)
     data List a r = Nil | Cons a r

Also, if you know a certain collection of component types must always 
occur together, then you can flatten parts of the coproduct and use 
normal unions as well. E.g.

     data Odd  r = One | Three
     data Two  r = Two
     data Four r = Four
     type Foo    = Fix (Odd :+: Two :+: Four)

Live well,

More information about the Haskell-Cafe mailing list