On 9/28/07, ok <[EMAIL PROTECTED]> 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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
