[project @ 2001-02-26 09:29:32 by simonpj]

[ghc-hetmet.git] / ghc / lib / std / PrelList.lhs

diff --git a/ghc/lib/std/PrelList.lhs b/ghc/lib/std/PrelList.lhs
index 7b85297..7453388 100644 (file)
--- a/ghc/lib/std/PrelList.lhs
+++ b/ghc/lib/std/PrelList.lhs
@@ -1,5 +1,7 @@
+% ------------------------------------------------------------------------------
+% $Id: PrelList.lhs,v 1.23 2001/02/26 09:29:32 simonpj Exp $
 %
-% (c) The AQUA Project, Glasgow University, 1994-1996
+% (c) The University of Glasgow, 1994-2000
 %
 
 \section[PrelList]{Module @PrelList@}
@@ -7,7 +9,7 @@
 The List data type and its operations
 
 \begin{code}
-{-# OPTIONS -fcompiling-prelude -fno-implicit-prelude #-}
+{-# OPTIONS -fno-implicit-prelude #-}
 
 module PrelList (
    [] (..),
@@ -21,7 +23,6 @@ module PrelList (
    any, all, elem, notElem, lookup,
    maximum, minimum, concatMap,
    zip, zip3, zipWith, zipWith3, unzip, unzip3,
-
 #ifdef USE_REPORT_PRELUDE
 
 #else
@@ -125,10 +126,19 @@ filterFB c p x r | p x       = x `c` r
 
 {-# RULES
 "filter"       forall p xs.    filter p xs = build (\c n -> foldr (filterFB c p) n xs)
-"filterFB"     forall c p q.   filterFB (filterFB c p) q = filterFB c (\x -> p x && q x)
+"filterFB"     forall c p q.   filterFB (filterFB c p) q = filterFB c (\x -> q x && p x)
 "filterList"   forall p.       foldr (filterFB (:) p) [] = filterList p
  #-}
 
+-- Note the filterFB rule, which has p and q the "wrong way round" in the RHS.
+--     filterFB (filterFB c p) q a b
+--   = if q a then filterFB c p a b else b
+--   = if q a then (if p a then c a b else b) else b
+--   = if q a && p a then c a b else b
+--   = filterFB c (\x -> q x && p x) a b
+-- I originally wrote (\x -> p x && q x), which is wrong, and actually
+-- gave rise to a live bug report.  SLPJ.
+
 filterList :: (a -> Bool) -> [a] -> [a]
 filterList _pred []    = []
 filterList pred (x:xs)
@@ -147,9 +157,15 @@ filterList pred (x:xs)
 -- scanl1 is similar, again without the starting element:
 --      scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
 
-foldl                   :: (a -> b -> a) -> a -> [b] -> a
-foldl _ z []            =  z
-foldl f z (x:xs)        =  foldl f (f z x) xs
+-- We write foldl as a non-recursive thing, so that it
+-- can be inlined, and then (often) strictness-analysed,
+-- and hence the classic space leak on foldl (+) 0 xs
+
+foldl        :: (a -> b -> a) -> a -> [b] -> a
+foldl f z xs = lgo z xs
+            where
+               lgo z []     =  z
+               lgo z (x:xs) = lgo (f z x) xs
 
 foldl1                  :: (a -> a -> a) -> [a] -> a
 foldl1 f (x:xs)         =  foldl f x xs
@@ -425,8 +441,11 @@ concatMap               :: (a -> [b]) -> [a] -> [b]
 concatMap f             =  foldr ((++) . f) []
 
 concat :: [[a]] -> [a]
-{-# INLINE concat #-}
 concat = foldr (++) []
+
+{-# RULES
+  "concat" forall xs. concat xs = build (\c n -> foldr (\x y -> foldr c y x) n xs)
+ #-}
 \end{code}
 
 
@@ -483,6 +502,16 @@ foldr2_right  k _z  y  r (x:xs) = k x y (r xs)
  #-}
 \end{code}
 
+The foldr2/right rule isn't exactly right, because it changes
+the strictness of foldr2 (and thereby zip)
+
+E.g. main = print (null (zip nonobviousNil (build undefined)))
+          where   nonobviousNil = f 3
+                  f n = if n == 0 then [] else f (n-1)
+
+I'm going to leave it though.
+
+
 zip takes two lists and returns a list of corresponding pairs.  If one
 input list is short, excess elements of the longer list are discarded.
 zip3 takes three lists and returns a list of triples.  Zips for larger