I'm looking for a paper or tutorial which compares/contrasts generalized algebraic data types and type classes (as found in GHC/Haskell). I get the feeling that they are some how duals of each other, and that there may be some overlap of the capabilities of each, but I don't know if I understand the essential differences which makes both desirable. For example, the standard GADT example of a tagless interpreter looks pretty similar to an equivalent built using type classes. In fact, the code for "
eval
" is identical, only the type annotations differ. Any thoughts, comments?
data Term a where
Lit :: Int -> Term Int
Inc :: Term Int -> Term Int
IsZ :: Term Int -> Term Bool
If :: Term Bool -> Term a -> Term a -> Term a
Pair :: Term a -> Term b -> Term (a,b)
Fst :: Term (a,b) -> Term a
Snd :: Term (a,b) -> Term b
eval :: Term a -> a
eval (Lit i) = i
eval (Inc t) = eval t + 1
eval (IsZ t) = eval t == 0
eval (If b t e) = if eval b then eval t else eval e
eval (Pair a b) = (eval a, eval b)
eval (Fst t) = fst (eval t)
eval (Snd t) = snd (eval t)
data Inc a = Inc a
data Lit a = Lit a
data IsZ a = IsZ a
data Pair a b = Pair a b
data If p t e = If p t e
data Fst a = Fst a
data Snd a = Snd a
class Eval a b | a -> b where eval :: a -> b
instance Eval (Lit a) a where eval (Lit i) = i
instance (Num b, Eval a b) => Eval (Inc a) b where eval (Inc t) = eval t + 1
instance (Num b, Eval a b) => Eval (IsZ a) Bool where eval (IsZ t) = eval t == 0
instance (Eval a Bool, Eval b d, Eval c d) =>
Eval (If a b c) d where eval (If p t e) = if eval p
then eval t
else eval e
instance (Eval a c, Eval b d) =>
Eval (Pair a b) (c,d) where eval (Pair a b) = (eval a, eval b)
instance (Eval a (b,c)) => Eval (Fst a) b where eval (Fst t) = fst (eval t)
instance (Eval a (b,c)) => Eval (Snd a) c where eval (Snd t) = snd (eval t)
...and here's a driver program which will work for either snippet...
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-undecidable-instances #-}
main = print $ (eval stuff)
stuff = Pair (If (IsZ (Inc (Inc (Lit 5))))
(Lit 6)
(Lit 7))
(Fst (Snd (Pair (Lit 42)
(Pair (Lit 8) (Lit 9)))))
Recent comments
17 weeks 11 hours ago
17 weeks 11 hours ago
17 weeks 11 hours ago
23 weeks 21 hours ago
1 year 11 weeks ago
1 year 11 weeks ago
1 year 11 weeks ago
1 year 33 weeks ago
1 year 37 weeks ago
1 year 39 weeks ago