I was trying to understand the Article The Operational Monad Tutorial by Heinrich Apfelmus, where he uses GADTs a lot. As a mental exercise, I tried to rewrite his code-examples so they no longer use GADTs. I couldn't do it, and now I am usure whether this is because of my limited skills, or if there is a fundamental issue.
On r/haskell Edward Kmett states that "You can always transform a GADT into a finally [sic] tagless representation through a class if you have Rank N types."
But what if I don't want to use Rank N types either? I suppose, I'd have to sacrifice something, but I should still be able to do it.
So, if I'm willing to sacrifice some type safety, use phantom types, typeclasses and whatnot, can I then write an eval function for expressions (somewhat) like the ones below, without using LANGUAGE extensions?
-- using GADTs :
data Expr = I Int | -- Int -> Expr Int
B Bool | -- Bool -> Expr Bool
Add Expr Expr -- Expr Int -> Expr Int -> Expr Int
Eq Expr Expr -- Expr 1 -> Expr a -> Expr Bool
Without GADTs, you don't know whether Expr is well-typed, so you can only implement an eval which possibly throws errors.
eval :: Expr -> Maybe (Either Int Bool)
eval (I n) = pure (Left n)
eval (B b) = pure (Right b)
eval (Add e1 e2) = do
x1 <- eval e1
x2 <- eval e2
case (x1, x2) of
(Left n1, Left n2) -> pure (Left (n1 + n2))
_ -> Nothing
eval (Eq e1 e2) = do
x1 <- eval e1
x2 <- eval e2
case (x1, x2) of
(Left n1, Left n2) -> pure (Right (n1 == n2))
(Right b1, Right b2) -> pure (Right (b1 == b2))
_ -> Nothing