[Haskell-cafe] Evaluating an AST with GADTs (and Type Families?)

Hilco Wijbenga hilco.wijbenga at gmail.com
Wed Aug 7 03:28:34 UTC 2019

Hi all,

I'm trying to implement an evaluator with GADTs. This is about as far
as I've gotten: https://pastebin.com/XjWBzgw7 .

data Value
    = ValueBool Bool
    | ValueText String
    | ValueObject (Map String Value)

data Expr t where
    ExprBool :: Bool -> Expr Bool
    ExprBoolOr :: Expr Bool -> Expr Bool -> Expr Bool
    ExprText :: String -> Expr String
    ExprTextAppend :: Expr String -> Expr String -> Expr String
    ExprObject :: Map String Value -> String -> Expr Value

eval :: Expr t -> t
eval (ExprBool value) = value
eval (ExprBoolOr lft rgt) = eval lft || eval rgt
eval (ExprText value) = value
eval (ExprTextAppend lft rgt) = eval lft <> eval rgt
eval (ExprObject map fieldName) = map ! fieldName

Note that the Value data type was just an attempt and not
(necessarily) what I'm looking for. And I'm ignoring all error
handling for the moment to keep the example small.

This compiles but obviously the object type is completely separate
from the Expr Bool and Expr String types. Apparently, Type Familiies
might help here? I could not find anything relevant that really
explained it.

I've been thinking about changing ExprObject to something like

ExprObjectBool :: Map String Value -> String -> Expr Bool
ExprObjectString :: Map String Value -> String -> Expr String
ExprObjectObject :: Map String Value -> String -> Expr ???

but I can't figure out what ??? would be. And this would seem to
explode if I add more "primitive" types, especially if I want to
support lists and maps as well. (Maps and objects are very similar but
not the same.)

How would I go about making the object type useful here? Or should I
go back to plain "Expr" and just error out when trying to, e.g., "or"
2 Strings?


More information about the Haskell-Cafe mailing list