In Paul Hudak's SOE, I find a definition of expression:

data Expr = C Float | V String | Expr :+ Expr | Expr :- Expr | Expr :* Expr | Expr :/ Expr

Now this is compelling, but sometimes, I might want to have a function that takes a variable only, not just any kind of expression. I could write something like:

typeOfVariable :: Expression -> Type typeOfVariable (V s) = ... _ = error...

But thats not very satisfying from a type-checking perspective. So it makes sense to create a constructor:

data Variable = VVariable String

data Expr = C Float | V Variable | Expr :+ Expr | Expr :- Expr | Expr :* Expr | Expr :/ Expr

and make typeOfVariable :: Variable -> Type. But then when I want to match or create a variable expression, things are starting to get verbose:

case expr of C f -> ... V (Variable (VVariable s)) -> ... ...

I think you mean: case expr of C f -> ... V (VVariable s) -> ... which is not quite as verbose.

And if I want a still more accurate hierarchy, the construction and destruction of Variables can really become cumbersome. For an interpreter I'm writing, I found myself writing a function "constructVarExpr :: String -> Expr" just to make it easier. This all seems very inelegant, and I get the feeling that there's a better way to do this.

Any suggestions on how I could better represent Expressions or Variables to keep the type-checking but decrease the verbosity?

I don't think that the problem is as bad as you make it out to be. If you adopt my use of short constructor names, then something like: data Var = Var String data Expr = C Float | V Var | Expr :+ Expr | Expr :- Expr | Expr :* Expr | Expr :/ Expr is quite concise, as is: case expr of C f -> ... V (Var s) -> ... Also I don't see the point of defining constructVarExpr since "constructVarExpr s" is not much clearer or shorter than "V (Var s)". On the other hand, there are much deeper issues at play here regarding the representation of a language with variables as a data type. What I did in my book was very simple, and the use of variables was only given as an exercise (by the way, you left out the "Let" constructor, which presuambly has the form "Let String Expr"). Ideally you will also want to express polymorphism and properly-typed higher-order functions, which gets into the use of "phantom types". A more recent idea is to use "higher-order abstract syntax", in which variables and functions of the language being implemented (often called the "object language") are modelled as variables and functions in the implementation language (often called the "meta language"), i.e. Haskell. For a good explanation of this, see Morton Rhiger's paper "A simple take on typed abstract syntax in Haskell-like languages" at: http://www.brics.dk/~mrhiger/daimi-pub.html Hope this helps, -Paul

Variable (VVariable(varName, (Value (Number (NNumber (varValue, varDimension))))))

Here VVariable and NNumber are newtype constructors of tuples, and the entire expression is an "Expression" which, among other things has:

data Expression = Value Value | Variable Variable | ...

and Value has "data Value = Number Number | ..."

Now the newtype constructors seem a bit unnecessary, perhaps, but I guess they increase the type-checking. So I still feel that the above construtor is overly verbose.

Not every embedding has to add constructors. If you look at the types: VVariable :: (String,Value) -> Variable Variable :: Variable -> Expression, you see that you are just using the constructor as a simple way to embed your subtype of variables in the type of expressions. To leave out the intermediate constructor, redefine data Expression = .. | Variable (String,Value) | .. and write your own embedding function, with the same type as the old constructor, that does not preserve the intermediate constructor: variable :: Variable -> Expression variable (VVariable (s,v)) = Variable (s,v) However, my real reason for posting is to recommend a paper you might enjoy, which deals with extensible union types in the context of interpreters, using type classes to automate the embeddings: Monad Transformers and Modular Interpreters, Sheng Liang, Paul Hudak, and Mark P. Jones, In Conference Record of POPL'95: 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, San Francisco, CA, January 1995. http://www.cse.ogi.edu/~mpj/pubs/modinterp.html Hth, Claus -- Haskell Communities and Activities Report (November 2002 edition) All contributions are due in by the end of October! http://www.haskell.org/communities/