From ab6fcc27c7f36115460bf7ae69777948cd2ddd81 Mon Sep 17 00:00:00 2001
From: chak <unknown>
Date: Mon, 11 Feb 2002 08:58:43 +0000
Subject: [PATCH] [project @ 2002-02-11 08:58:43 by chak] Updated to the use
 of [~N] in rules implementing foldr/build.

---
 ghc/docs/comm/rts-libs/prelude.html |   43 +++++++++++++++++++++++++++++++----
 1 file changed, 39 insertions(+), 4 deletions(-)

diff --git a/ghc/docs/comm/rts-libs/prelude.html b/ghc/docs/comm/rts-libs/prelude.html
index 3f12bb1..72147ab 100644
--- a/ghc/docs/comm/rts-libs/prelude.html
+++ b/ghc/docs/comm/rts-libs/prelude.html
@@ -21,8 +21,43 @@
       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
@@ -51,11 +86,11 @@ mapList f (x:xs) = f x : mapList f xs
       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>
-- 
1.7.10.4