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
1 day 19 hours ago
2 days 4 min ago
2 days 8 hours ago
2 days 17 hours ago
3 days 35 min ago
3 days 19 hours ago
5 days 2 hours ago
5 days 12 hours ago
5 days 22 hours ago
6 days 1 hour ago