+% ------------------------------------------------------------------------------
+% $Id: PrelList.lhs,v 1.22 2000/09/14 13:46:42 simonpj Exp $
%
-% (c) The AQUA Project, Glasgow University, 1994-1996
+% (c) The University of Glasgow, 1994-2000
%
\section[PrelList]{Module @PrelList@}
any, all, elem, notElem, lookup,
maximum, minimum, concatMap,
zip, zip3, zipWith, zipWith3, unzip, unzip3,
+#ifdef USE_REPORT_PRELUDE
+
+#else
-- non-standard, but hidden when creating the Prelude
-- export list.
takeUInt_append
+#endif
+
) where
import {-# SOURCE #-} PrelErr ( error )
head :: [a] -> a
head (x:_) = x
-head [] = errorEmptyList "head"
+head [] = badHead
+
+badHead = errorEmptyList "head"
+
+-- This rule is useful in cases like
+-- head [y | (x,y) <- ps, x==t]
+{-# RULES
+"head/build" forall (g::forall b.(Bool->b->b)->b->b) .
+ head (build g) = g (\x _ -> x) badHead
+"head/augment" forall xs (g::forall b. (a->b->b) -> b -> b) .
+ head (augment g xs) = g (\x _ -> x) (head xs)
+ #-}
tail :: [a] -> [a]
tail (_:xs) = xs
-- elements that satisfy the predicate; i.e.,
-- filter p xs = [ x | x <- xs, p x]
filter :: (a -> Bool) -> [a] -> [a]
-{-# INLINE filter #-}
-filter p xs = build (\c n -> foldr (filterFB c p) n xs)
+filter = filterList
filterFB c p x r | p x = x `c` r
| otherwise = r
{-# RULES
-"filterFB" forall c,p,q. filterFB (filterFB c p) q = filterFB c (\x -> p x && q x)
+"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 -> 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)
-- iterate f x returns an infinite list of repeated applications of f to x:
-- iterate f x == [x, f x, f (f x), ...]
iterate :: (a -> a) -> a -> [a]
-{-# INLINE iterate #-}
-iterate f x = build (\c n -> iterateFB c f x)
+iterate = iterateList
iterateFB c f x = x `c` iterateFB c f (f x)
iterateList f x = x : iterateList f (f x)
{-# RULES
-"iterate" iterateFB (:) = iterateList
+"iterate" forall f x. iterate f x = build (\c _n -> iterateFB c f x)
+"iterateFB" iterateFB (:) = iterateList
#-}
-- repeat x is an infinite list, with x the value of every element.
repeat :: a -> [a]
-{-# INLINE repeat #-}
-repeat x = build (\c n -> repeatFB c x)
+repeat = repeatList
repeatFB c x = xs where xs = x `c` xs
repeatList x = xs where xs = x : xs
{-# RULES
-"repeat" repeatFB (:) = repeatList
+"repeat" forall x. repeat x = build (\c _n -> repeatFB c x)
+"repeatFB" repeatFB (:) = repeatList
#-}
-- replicate n x is a list of length n with x the value of every element
take :: Int -> [a] -> [a]
take 0 _ = []
take _ [] = []
-take n (x:xs) | n > 0 = x : take (n-1) xs
+take n (x:xs) | n > 0 = x : take (minusInt n 1) xs
take _ _ = errorNegativeIdx "take"
drop :: Int -> [a] -> [a]
drop 0 xs = xs
drop _ [] = []
-drop n (_:xs) | n > 0 = drop (n-1) xs
+drop n (_:xs) | n > 0 = drop (minusInt n 1) xs
drop _ _ = errorNegativeIdx "drop"
splitAt :: Int -> [a] -> ([a],[a])
splitAt 0 xs = ([],xs)
splitAt _ [] = ([],[])
-splitAt n (x:xs) | n > 0 = (x:xs',xs'') where (xs',xs'') = splitAt (n-1) xs
+splitAt n (x:xs) | n > 0 = (x:xs',xs'') where (xs',xs'') = splitAt (minusInt n 1) xs
splitAt _ _ = errorNegativeIdx "splitAt"
#else /* hack away */
or (x:xs) = x || or xs
{-# RULES
-"and/build" forall g::forall b.(Bool->b->b)->b->b .
+"and/build" forall (g::forall b.(Bool->b->b)->b->b) .
and (build g) = g (&&) True
-"or/build" forall g::forall b.(Bool->b->b)->b->b .
+"or/build" forall (g::forall b.(Bool->b->b)->b->b) .
or (build g) = g (||) False
#-}
#endif
all _ [] = True
all p (x:xs) = p x && all p xs
{-# RULES
-"any/build" forall p, g::forall b.(a->b->b)->b->b .
+"any/build" forall p (g::forall b.(a->b->b)->b->b) .
any p (build g) = g ((||) . p) False
-"all/build" forall p, g::forall b.(a->b->b)->b->b .
+"all/build" forall p (g::forall b.(a->b->b)->b->b) .
all p (build g) = g ((&&) . p) True
#-}
#endif
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}
(!!) :: [a] -> Int -> a
#ifdef USE_REPORT_PRELUDE
(x:_) !! 0 = x
-(_:xs) !! n | n > 0 = xs !! (n-1)
+(_:xs) !! n | n > 0 = xs !! (minusInt n 1)
(_:_) !! _ = error "Prelude.(!!): negative index"
[] !! _ = error "Prelude.(!!): index too large"
#else
%*********************************************************
\begin{code}
-foldr2 k z [] ys = z
-foldr2 k z xs [] = z
+foldr2 _k z [] _ys = z
+foldr2 _k z _xs [] = z
foldr2 k z (x:xs) (y:ys) = k x y (foldr2 k z xs ys)
-foldr2_left k z x r [] = z
-foldr2_left k z x r (y:ys) = k x y (r ys)
+foldr2_left _k z _x _r [] = z
+foldr2_left k _z x r (y:ys) = k x y (r ys)
-foldr2_right k z y r [] = z
-foldr2_right k z y r (x:xs) = k x y (r xs)
+foldr2_right _k z _y _r [] = z
+foldr2_right k _z y r (x:xs) = k x y (r xs)
-- foldr2 k z xs ys = foldr (foldr2_left k z) (\_ -> z) xs ys
-- foldr2 k z xs ys = foldr (foldr2_right k z) (\_ -> z) ys xs
{-# RULES
-"foldr2/left" forall k,z,ys,g::forall b.(a->b->b)->b->b .
+"foldr2/left" forall k z ys (g::forall b.(a->b->b)->b->b) .
foldr2 k z (build g) ys = g (foldr2_left k z) (\_ -> z) ys
-"foldr2/right" forall k,z,xs,g::forall b.(a->b->b)->b->b .
+"foldr2/right" forall k z xs (g::forall b.(a->b->b)->b->b) .
foldr2 k z xs (build g) = g (foldr2_right k z) (\_ -> z) 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
\begin{code}
----------------------------------------------
zip :: [a] -> [b] -> [(a,b)]
-{-# INLINE zip #-}
-zip xs ys = build (\c n -> foldr2 (zipFB c) n xs ys)
+zip = zipList
zipFB c x y r = (x,y) `c` r
zipList _ _ = []
{-# RULES
-"zipList" foldr2 (zipFB (:)) [] = zipList
+"zip" forall xs ys. zip xs ys = build (\c n -> foldr2 (zipFB c) n xs ys)
+"zipList" foldr2 (zipFB (:)) [] = zipList
#-}
\end{code}
\begin{code}
----------------------------------------------
zipWith :: (a->b->c) -> [a]->[b]->[c]
-{-# INLINE zipWith #-}
-zipWith f xs ys = build (\c n -> foldr2 (zipWithFB c f) n xs ys)
+zipWith = zipWithList
+
zipWithFB c f x y r = (x `f` y) `c` r
zipWithList :: (a->b->c) -> [a] -> [b] -> [c]
zipWithList f (a:as) (b:bs) = f a b : zipWithList f as bs
-zipWithList f _ _ = []
+zipWithList _ _ _ = []
{-# RULES
-"zipWithList" forall f. foldr2 (zipWithFB (:) f) [] = zipWithList f
+"zipWith" forall f xs ys. zipWith f xs ys = build (\c n -> foldr2 (zipWithFB c f) n xs ys)
+"zipWithList" forall f. foldr2 (zipWithFB (:) f) [] = zipWithList f
#-}
\end{code}
-- unzip transforms a list of pairs into a pair of lists.
unzip :: [(a,b)] -> ([a],[b])
+{-# INLINE unzip #-}
unzip = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
unzip3 :: [(a,b,c)] -> ([a],[b],[c])
+{-# INLINE unzip3 #-}
unzip3 = foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
([],[],[])
\end{code}
projects / ghc-hetmet.git / blobdiff