[clean-list] Transform to CPS

[Simon Peyton-Jones]

| function posted by the originator of this thread.  If my recollection
is
| correct, GHC can only optimize away intermediate lists, not other
| intermediate data structures (e.g. trees), and only if they are
| constructed and consumed by list processing functions which are
ultimately
| defined in terms of a couple of built-in higher-order functions, not
| if they are constructed or consumed using manual first-order code that
| processes each element in turn.

Correct.

| The Melbourne Mercury compiler has had support for deforestation since
| Mercury 0.8, released on 18 November 1998.  It supports a quite
general
| form of deforestation that is capable of deforesting intermediate
| data structures of user-defined types such as trees.

I didn't know that -- I'm well impressed.  One the hardest aspects, I
found, was to guarantee that the transformation would never make things
worse.  For example, transforming a function that consumes a data
structure directly, to use a fold instead, makes it less efficient.
Ditto on the 'production' side.  So there has to be a way to make sure
that when fusion does not happen, the program is no less efficient than
before.  Is this the case in Mercury?

 Is the MSc thesis you refer to available online?

Simon