Please help find a paper/tutorial


I wanted to reread a paper that discusses how to extend data types in Haskell in a flexible way.
The paper was motivated by an evaluator example that can evaluate additions.
Suppose now multiplication expressions also need to be supported, then every function that looks into the data type that represents expressions must be changed.
The idea of this paper was to introduce an extra indirection layer and define recursive types in a roundabout way. For example natural numbers can be defined as:

newtype Mu f = In (f (Mu f))
data NatF b = Zero | Succ b
type Nat = Mu NatF

Now 0 is encoded as In Zero, 1 as In $ Succ (In Zero), etc.

The paper then goes on talking about building higher-order functions in this more flexible framework.

I'm not looking for the original papers on catamorphisms and catamorphisms.
This paper is rather a tutorial that builds on top of those ideas.
I couldn't recall the title or the author.
I thought it was in functional pearls but couldn't find it.

Thanks for your help.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Wouter Swierstra's "Data Types á là Carte"?

Maybe this is Wouter Swierstra's as-yet-unpublished (I think) functional pearl called "Data Types á là Carte"?

If not, I suspect the one you want might be found in his references (or in their refs., etc.). Or you might try using "expression problem" as one of your search terms.

Hope this helps!

That's exactly what I want.

That's exactly what I want.

Sounds similar to ...

It's clearly not the paper specifically sought, but the question reminded me of Steele's "Building Interpreters by Composing Monads"