[Haskell-cafe] extensible data types in Haskell?

Pablo Nogueira pablo at babel.ls.fi.upm.es
Tue Jul 8 04:19:01 EDT 2008


I prefer Bruno's approach, though. It allows meta-level type-checking
of expressions and there's the possibility of closing the extension
with a wrapper:
(References: "Generics as a Library" and his PhD thesis)

- GADT as a type class (or encode the type as it's fold):

 class Exp e where
     lit  :: TyRange a => a -> e a
     plus :: e Int -> e Int -> e Int
     and  :: e Bool -> e Bool -> e Bool

- Notice we cannot construct an ill-typed expression, the Haskell
type-checker complains.

- |TyRange| is the class of indices:

class TyRange a
instance TyRange Int
instance TyRange Bool

- The behaviour is given by instances:

newtype Eval a = Eval {eval :: a}

instance Exp Eval where
     lit       = Eval
     plus x y  = Eval (eval x + eval y)
     and  x y  = Eval (eval x && eval y)

Extension is easy:

class Exp e => ExpIf e where
   ifOp :: TyRange a => e Bool -> e a -> e a -> e a

instance ExpIf Eval where
   ifOp c t e = Eval (if (eval c) then (eval t) else (eval e))

class Exp e => ExpMult e where
    mult :: e Int -> e Int -> e Int

instance ExpMult Eval where
    mult x y = Eval (eval x * eval y)

- Adding new meta-level types is easy:

instance TyRange a => TyRange [a]
instance TyRange Char

class Exp e => ExpConcat e where
    conc :: e [Char] -> e [Char] -> e [Char]

instance ExpConcat Eval where
    conc x y = Eval (eval x ++ eval y)

- Closing expressions is also easy:  wrap around a type and provide
new functions:

data TyRange a => Wrap a = Wrap (forall e. (Exp e, ExpIf e, ExpMult e,
ExpConcat e) => e a)

> evalExp :: TyRange a => Wrap a -> a
> evalExp (Wrap x) = eval x

- Some expresions:

Compare:

exp1 :: Exp e => e Int
exp1 = plus (lit 3) (lit 3)
val1 = eval exp1

With:

exp1' :: Eval Int
exp1' = plus (lit 3) (lit 3)
va1'  = eval exp1


More information about the Haskell-Cafe mailing list