Obviously you are modelling the datatype
-- data Expr = Add Expr Expr | Sub Expr Expr | Mul Expr Expr | Div
Expr Expr | Num Int
You already have ExprF, and now you need to throw in Fix
newtype Fix f = In (f(Fix f))
in order to be able to build Expr like terms.
type Expr' = Fix ExprF
add a b = In (Add a b)
sub a b = In (Sub a b)
....
I've heard people refer to this technique of modelling datatypes as
taking the initial algebra of the associated endofunctor (in this case
ExprF) [http://strictlypositive.org/indexed-containers.pdf]
This pattern is discussed in depth in Jeremy Gibbons work. I really
recommend his "Datatype-Generic Programming" piece [http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/dgp.pdf
].
Someone else mentioned the multirec library. If you feel really
adventurous you can look at the paper behind: "Generic programming
with fixed points for mutually recursive datatypes" [http://people.cs.uu.nl/andres/Rec/MutualRec.pdf] or check out Andres presentation at ICFP [http://vimeo.com/6612724
].
Just my 2c.
On 22/10/2009, at 09:47, Martijn van Steenbergen wrote:
Bonjour café,
data ExprF r
= Add r r
| Sub r r
| Mul r r
| Div r r
| Num Int
This is a well-known pattern that for example allows nice notation
of morphisms. But what is it called? I've heard fixed-point view,
open datatypes and some others, but I'm curious where this pattern
comes up in literature and what it is called there.
Thanks,
Martijn.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
