haskell - Converting an untyped AST for a simple typed language into a GADT -

i have adt representing ast simple language:

data uterm = utrue       | ufalse       | uif uterm uterm uterm       | uzero       | usucc uterm       | uiszero uterm 

this data structure can represent invalid terms don't follow type rules of language, uiszero ufalse, i'd use gadt enforces well-typedness:

{-# language gadts #-}  data tterm   ttrue :: tterm bool   tfalse :: tterm bool   tif :: tterm bool -> tterm -> tterm -> tterm   tzero :: tterm int   tsucc :: tterm int -> tterm int   tiszero :: tterm int -> tterm bool 

my problem type check uterm , convert tterm. first thought uterm -> maybe (tterm a), of course doesn't work because it's not valid as. don't know type be, because don't know if a going int or bool. thought write different type checking function each of possible values of a:

import control.applicative  typecheckbool :: uterm -> maybe (tterm bool) typecheckbool utrue = ttrue typecheckbool ufalse = tfalse typecheckbool (uiszero a) = tiszero <$> typecheckint typecheckbool _ = nothing  typecheckint :: uterm -> maybe (tterm int) typecheckint uzero = tzero typecheckint (usucc a) = tsucc <$> typecheckint typecheckint (uif b c) = tif <$> typecheckbool <*> typecheckint b <*> typecheckint c typecheckint utrue = nothing typecheckint ufalse = nothing typecheckint (uiszero _) = nothing 

this works cases, subset of language tif requires consequent , alternative ints (but tif ttrue tfalse ttrue totally valid), , know target type of expression we're typing.

what's right way convert uterm tterm?

the standard technique define existential type:

data eterm_     eterm_ :: tterm -> eterm 

in case, may want term-level evidence of type have; e.g.

data type     tint :: type int     tbool :: type bool 

then real eterm this:

data eterm     eterm :: type -> tterm -> eterm 

the interesting case of type checking like

typecheck (uif ucond ut uf) =     eterm tbool tcond <- typecheck ucond     eterm tyt tt <- typecheck ut     eterm tyf tf <- typecheck uf     case (tyt, tyf) of         (tbool, tbool) -> return (eterm tbool (tif tcond tt tf))         (tint , tint ) -> return (eterm tint  (tif tcond tt tf))         _ -> fail "branches have different types"