pragmas</a> implementing the <a
href="http://research.microsoft.com/Users/simonpj/Papers/deforestation-short-cut.ps.Z">fold/build</a>
optimisation. The code for <code>map</code> is
- a good example for how it all works. In the prelude code for version
- 4.08.1 it reads as follows:
+ a good example for how it all works. In the prelude code for version
+ 5.03 it reads as follows:
+ <blockquote><pre>
+map :: (a -> b) -> [a] -> [b]
+map _ [] = []
+map f (x:xs) = f x : map f xs
+
+-- Note eta expanded
+mapFB :: (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
+{-# INLINE [0] mapFB #-}
+mapFB c f x ys = c (f x) ys
+
+{-# RULES
+"map" [~1] forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)
+"mapList" [1] forall f. foldr (mapFB (:) f) [] = map f
+"mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g)
+ #-}</pre>
+ </blockquote>
+ <p>
+ Up to (but not including) phase 1, we use the <code>"map"</code> rule to
+ rewrite all saturated applications of <code>map</code> with its
+ build/fold form, hoping for fusion to happen. In phase 1 and 0, we
+ switch off that rule, inline build, and switch on the
+ <code>"mapList"</code> rule, which rewrites the foldr/mapFB thing back
+ into plain map.
+ <p>
+ It's important that these two rules aren't both active at once
+ (along with build's unfolding) else we'd get an infinite loop
+ in the rules. Hence the activation control using explicit phase numbers.
+ <p>
+ The "mapFB" rule optimises compositions of map.
+ <p>
+ The mechanism as described above is new in 5.03 since January 2002,
+ where the <code>[~</code><i>N</i><code>]</code> syntax for phase number
+ annotations at rules was introduced. Before that the whole arrangement
+ was more complicated, as the corresponding prelude code for version
+ 4.08.1 shows:
<blockquote><pre>
map :: (a -> b) -> [a] -> [b]
map = mapList
before any of the foldr/build rules fires). To make the timing
deterministic, <code>build</code> gets a <code>{-# INLINE 2 build
#-}</code> pragma, which delays <code>build</code>'s inlining, and thus,
- the closing of the map.
+ the closing of the map. [NB: Phase numbering was forward at that time.]
<p><small>
<!-- hhmts start -->
-Last modified: Wed Aug 8 19:31:18 EST 2001
+Last modified: Mon Feb 11 20:00:49 EST 2002
<!-- hhmts end -->
</small>
</body>