Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Typed AST with GADT in Haskell
{-# LANGUAGE GADTs #-} -- You need GADTs pragma.
data Exp r where
Const :: (Show r) => r -> Exp r
Add :: (Num r) => Exp r -> Exp r -> Exp r
Subtract :: (Num r) => Exp r -> Exp r -> Exp r
Eq :: (Eq r) => Exp r -> Exp r -> Exp Bool
And :: Exp Bool -> Exp Bool -> Exp Bool
Or :: Exp Bool -> Exp Bool -> Exp Bool
eval :: Exp r -> r
eval (Const v) = v
eval (Add e1 e2) = (eval e1) + (eval e2)
eval (Subtract e1 e2) = (eval e1) - (eval e2)
eval (Eq e1 e2) = eval e1 == eval e2
eval (And e1 e2) = eval e1 && eval e2
eval (Or e1 e2) = eval e1 || eval e2
reify :: Exp r -> String
reify (Const v) = show v
reify (Add e1 e2) = concat ["(",reify e1,"+",reify e2,")"]
reify (Subtract e1 e2) = concat ["(",reify e1,"-",reify e2,")"]
reify (Eq e1 e2) = concat ["(",reify e1,"==",reify e2,")"]
reify (And e1 e2) = concat ["(",reify e1,"&&",reify e2,")"]
reify (Or e1 e2) = concat ["(",reify e1,"||",reify e2,")"]
main :: IO ()
main = do
putStrLn $ reify exp1
putStrLn $ reify exp2
putStrLn $ show $ eval exp2
putStrLn $ reify exp3
exp1 :: Exp Int
exp1 = Add (Const 3) (Const 2)
exp2 :: Exp Bool
exp2 = Eq (Const 3) (Const (2::Int))
exp3 :: Exp Bool
exp3 = And (Eq (Const 3) (Const (2::Int))) (Const True)
{-
Results with GHCi:
*Main> main
(3+2)
(3==2)
False
((3==2)&&True)
*Main> :t (Add (Const 2) (Const 3))
(Add (Const 2) (Const 3)) :: (Num r, Show r) => Exp r
*Main> :t (Or (Const True) (Const False))
(Or (Const True) (Const False)) :: Exp Bool
*Main> :t (Or (Const 3) (Const 2))
<interactive>:1:12:
No instance for (Num Bool) arising from the literal `3'
Possible fix: add an instance declaration for (Num Bool)
In the first argument of `Const', namely `3'
In the first argument of `Or', namely `(Const 3)'
In the expression: (Or (Const 3) (Const 2))
*Main>
-}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment