[Haskell-cafe] 'data' syntax - a suggestion

[Bas van Dijk]

On 9/28/07, ok <ok at cs.otago.ac.nz> wrote:
> Now there's a paper that was mentioned about a month ago in this
> mailing list which basically dealt with that by splitting each type
> into two:  roughly speaking a bit that expresses the recursion and
> a bit that expresses the choice structure.

Would you like to give a link to that paper?


(the following is a bit offtopic)

In the 1995 paper[1]: "Bananas in Space: Extending Fold and Unfold to
Exponential Types", Erik Meijer and Graham Hutton showed a interesting
technique:

Your ADT:

data Expr env = Variable (Var env)
              | Constant Int
              | Unary String (Expr env)
              | Binary String (Expr env) (Expr env)

can be written without recursion by using a fixpoint newtype
combinator (not sure if this is the right name for it):

newtype Rec f = In { out :: f (Rec f) }

data Var env = Var env String

data E env e = Variable (Var env)
             | Constant Int
             | Unary String e
             | Binary String e e

type Expr env = Rec (E env)

example = In (Binary "+" (In (Constant 1)) (In (Constant 2)))

You can see that you don't have to name the recursive 'Expr env'
explicitly. However constructing a 'Expr' is a bit verbose because of
the 'In' newtype constructors.

regards,

Bas van Dijk

[1] http://citeseer.ist.psu.edu/293490.html