DData revision

[Alastair Reid]

> I belive that using an accumulator to avoid ++'s
> bad behaviour is the second most used optimisation in functional programs.
> [...] Wadler [...]
>
> If Haskell implementations would use this, programmers could really spare
> some efforts and programs would be clearer.

GHC does implement this kind of optimization to remove ++ and :.  They work 
pretty well (see Simon Peyton Jones' page for papers about it and follow 
citations to find other recent work on the topic).

In practice though, it is useful to have data structures, algorithms, etc. 
that already contain the optimization though.  Some of the major reasons are:

1) The analyses that drive the optimizations are fragile and hard to predict.  
When the optimization triggers, you can get a large speedup or dramatic 
reduction in memory consumption but then you make a small, insignificant 
change to your program, the optimization can't be applied an you get a large 
change in performance.  Lesson: predictable performance is an important 
property.

2) This particular class of optimizations contain a space-time tradeoff.  If 
the data structure is shared, we can save time by building one copy and using 
it multiple times or we can save space by building a fresh copy each time.  
How is the compiler to know which you want to apply?  For some programs, you 
want to save space, for others, you want to save time.  Indeed, for small 
datasets, you want to save time while for bigger datasets you often have to 
choose to save space at the cost of time.  Lesson: some programming decisions 
can't be automated.

--
Alastair Reid      www.haskell-consulting.com