Shin-Cheng Mu wrote:
g seed = [ z | (s1, s2) <- split seed, x <- g s1, y <- g s2, z <- join x y ]
The relation f was almost as simple as a replacing each constructor in Tree1 with one or more coresponding constructors in Tree2. They two can be fused together and becomes
fg seed = [ z | (s1, s2) <- split seed, x <- fg s1, y <- fg s2, z <- join' x y ]
The intermediate datatype Tree1 was thus eliminated.
The problem was: the fused program ran slower than the original one! At least if you measure the total running time (either via the UNIX time command or use the CPUTime module). The time reported in the GHC time profile indeed showed that the fused program is faster, though, if GC time is excluded.
We were quite curious why and my guess was: since f maps a Tree1 to more than one Tree2, in the two list comprehensions, the list produced by (fg s2) is much longer than (g s2). The fused program thus has to keep a longer list in memory. Worse heap residency results in more GCs. (Luckily GHC did not attempt to automatically perform the fusion for us! :) )
Note that you have done more than just deforestation. You have moved f through join, obtaining join'. Because as you say (fg s2) is much longer than (g s2), join' is applied more often than join was applied before. I don't know how expensive your join and join' are. Furthermore, deforestation itself does not reduce runtime very much. More important is the secondary effect that deforstation moves formerly separated expressions close to each other, so that further optimisations can take place. Maybe in your example there are not many further optimisations? In real life it is seldomly clear which transformations are optimisations... (maybe a different machine will yield different results again?). Ciao, Olaf -- OLAF CHITIL, Dept. of Computer Science, The University of York, York YO10 5DD, UK. URL: http://www.cs.york.ac.uk/~olaf/ Tel: +44 1904 434756; Fax: +44 1904 432767