% ------------------------------------------------------------------------------
-% $Id: PrelList.lhs,v 1.20 2000/06/30 13:39:35 simonmar Exp $
+% $Id: PrelList.lhs,v 1.23 2001/02/26 09:29:32 simonpj Exp $
%
% (c) The University of Glasgow, 1994-2000
%
"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)
-- 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
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}