[Haskell-cafe] What's this pattern called?

[Jose Iborra]

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe