Your post only showed adding functionality over the algebra, not new types on which the algebra operates (or "sorts", as they are otherwise known). In other words, you can't easily extend Expr
to support Boolean logic in addition to addition itself. For a concrete example, how could you represent ternary operators like in the expression 2 + 2 == 4 ? 1 : 2
, such that it's well typed and will never result in an exception? With GADTs, this is very simple to do:
data Expr a where
Lit :: Int -> Expr Int
Add :: Expr Int -> Expr Int -> Expr Int
Eq :: Expr Int -> Expr Int -> Expr Bool
If :: Expr Bool -> Expr Int -> Expr Int -> Expr Int
eval :: Expr a -> a
eval expr = case expr of
Lit n -> n
Add a b -> eval a + eval b
Eq a b -> eval a == eval b
If p a b -> if eval p then eval a else eval b
-- >> eval example == 1 => true
example :: Expr Int
example =
If ((Lit 2 `Add` Lit 2) `Eq` Lit 4) (Lit 1) (Lit 2)
I can't even find showings in my state.