+% ------------------------------------------------------------------------------
+% $Id: PrelList.lhs,v 1.25 2001/07/31 10:48:02 simonmar Exp $
%
-% (c) The AQUA Project, Glasgow University, 1994-1996
+% (c) The University of Glasgow, 1994-2000
%
\section[PrelList]{Module @PrelList@}
The List data type and its operations
\begin{code}
-{-# OPTIONS -fcompiling-prelude -fno-implicit-prelude #-}
+{-# OPTIONS -fno-implicit-prelude #-}
module PrelList (
[] (..),
any, all, elem, notElem, lookup,
maximum, minimum, concatMap,
zip, zip3, zipWith, zipWith3, unzip, unzip3,
-
#ifdef USE_REPORT_PRELUDE
#else
{-# 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)
-- 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
-- is equivalent to (take n xs, drop n xs).
#ifdef USE_REPORT_PRELUDE
take :: Int -> [a] -> [a]
-take 0 _ = []
+take n _ | n <= 0 = []
take _ [] = []
-take n (x:xs) | n > 0 = x : take (minusInt n 1) xs
-take _ _ = errorNegativeIdx "take"
+take n (x:xs) = x : take (n-1) xs
drop :: Int -> [a] -> [a]
-drop 0 xs = xs
+drop n xs | n <= 0 = xs
drop _ [] = []
-drop n (_:xs) | n > 0 = drop (minusInt n 1) xs
-drop _ _ = errorNegativeIdx "drop"
+drop n (_:xs) = drop (n-1) xs
-
-splitAt :: Int -> [a] -> ([a],[a])
-splitAt 0 xs = ([],xs)
-splitAt _ [] = ([],[])
-splitAt n (x:xs) | n > 0 = (x:xs',xs'') where (xs',xs'') = splitAt (minusInt n 1) xs
-splitAt _ _ = errorNegativeIdx "splitAt"
+splitAt :: Int -> [a] -> ([a],[a])
+splitAt n xs = (take n xs, drop n xs)
#else /* hack away */
take :: Int -> [b] -> [b]
takeUInt :: Int# -> [b] -> [b]
takeUInt n xs
| n >=# 0# = take_unsafe_UInt n xs
- | otherwise = errorNegativeIdx "take"
+ | otherwise = []
take_unsafe_UInt :: Int# -> [b] -> [b]
take_unsafe_UInt 0# _ = []
takeUInt_append :: Int# -> [b] -> [b] -> [b]
takeUInt_append n xs rs
| n >=# 0# = take_unsafe_UInt_append n xs rs
- | otherwise = errorNegativeIdx "take"
+ | otherwise = []
take_unsafe_UInt_append :: Int# -> [b] -> [b] -> [b]
take_unsafe_UInt_append 0# _ rs = rs
drop :: Int -> [b] -> [b]
drop (I# n#) ls
- | n# <# 0# = errorNegativeIdx "drop"
+ | n# <# 0# = []
| otherwise = drop# n# ls
where
drop# :: Int# -> [a] -> [a]
splitAt :: Int -> [b] -> ([b], [b])
splitAt (I# n#) ls
- | n# <# 0# = errorNegativeIdx "splitAt"
+ | n# <# 0# = ([], ls)
| otherwise = splitAt# n# ls
where
splitAt# :: Int# -> [a] -> ([a], [a])
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}
#-}
\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
-tuples are in the List library
+tuples are in the List module.
\begin{code}
----------------------------------------------
errorEmptyList fun =
error (prel_list_str ++ fun ++ ": empty list")
-errorNegativeIdx :: String -> a
-errorNegativeIdx fun =
- error (prel_list_str ++ fun ++ ": negative index")
-
prel_list_str :: String
prel_list_str = "Prelude."
\end{code}
projects / ghc-hetmet.git / blobdiff