Update! The final version is now available.
Andres Löh, Johan Jeuring, and I have submitted a paper to IFL 2009.
Pull-Ups, Push-Downs, and Passing It Around: Exercises in Functional Incrementalization
Abstract Programs in functional programming languages with algebraic datatypes are often datatype-centric and use folds or fold-like functions. Incrementalization of such a program can significantly improve its performance. Functional incrementalization separates the recursion from the calculation and significantly reduces redundant computation. In this paper, we motivate incrementalization with a simple example and present a library for transforming programs using upwards, downwards, and circular incrementalization. We also give a datatype-generic implementation for the library and demonstrate the incremental zipper, a zipper extended with attributes.
This is the result of work that has previously been mentioned on this blog:
- Smart constructors
- Incremental fold, a design pattern
- Incremental attributes
- Latest on the incremental fold and attributes
- "Upwards and downwards accumulations on trees" translated into Haskell
We would be happy to have any feedback.
Update! Here's the (completely messy, badly formatted, undocumented, and screwy) code used in the paper if you want to have a go at it.
Loved the source coloring.
ReplyDeleteSebastiaan Visser recently pointed me to the paper "Programming with Nested Types" by Johann and Ghani. So I tried to implement your ideas with HFuntors.
ReplyDeleteHere's inU for example:
type UpAlg h s = h (K s) :~> K s
inU :: HFunctor h => UpAlg h s -> h (Mu1 s h) :~> Mu1 s h
inU alg fx = in1 (unK $ alg (hfmap (K . ann) fx)) fx
Interestigly pullUp is not needed. (I'm using :~> for natural transformations and K for the constant functor.)
So far I failed to implement inD, so maybe it doesn't work with HFunctor, but I've got the feeling that it should be possible.
Ehm, never mind what I said about pullUp. There's not much difference in code, I just merged the algebra and the pullUp into one algebra, which you probably split up for a reason.
ReplyDeleteThe reason pullUp is needed is that the IncrU class contains the minimal interface necessary to create an instance for each type. It becomes more apparent when you see that the same inU is used for TreeU as for the pattern functors K, I, etc.
ReplyDelete