Have validate take into account stat test failures too.
[ghc.git] / libraries / base / GHC / List.lhs
1 \begin{code}
2 {-# LANGUAGE Trustworthy #-}
3 {-# LANGUAGE CPP, NoImplicitPrelude, ScopedTypeVariables, MagicHash #-}
4 {-# LANGUAGE BangPatterns #-}
5 {-# OPTIONS_HADDOCK hide #-}
6
7 -----------------------------------------------------------------------------
8 -- |
9 -- Module      :  GHC.List
10 -- Copyright   :  (c) The University of Glasgow 1994-2002
11 -- License     :  see libraries/base/LICENSE
12 --
13 -- Maintainer  :  cvs-ghc@haskell.org
14 -- Stability   :  internal
15 -- Portability :  non-portable (GHC Extensions)
16 --
17 -- The List data type and its operations
18 --
19 -----------------------------------------------------------------------------
20
21 module GHC.List (
22    -- [] (..),          -- built-in syntax; can't be used in export list
23
24    map, (++), filter, concat,
25    head, last, tail, init, uncons, null, length, (!!),
26    foldl, foldl', foldl1, foldl1', scanl, scanl1, scanl', foldr, foldr1,
27    scanr, scanr1, iterate, repeat, replicate, cycle,
28    take, drop, sum, product, maximum, minimum, splitAt, takeWhile, dropWhile,
29    span, break, reverse, and, or,
30    any, all, elem, notElem, lookup,
31    concatMap,
32    zip, zip3, zipWith, zipWith3, unzip, unzip3,
33    errorEmptyList,
34
35  ) where
36
37 import Data.Maybe
38 import GHC.Base
39 import GHC.Num (Num(..))
40 import GHC.Integer (Integer)
41
42 infixl 9  !!
43 infix  4 `elem`, `notElem`
44 \end{code}
45
46 %*********************************************************
47 %*                                                      *
48 \subsection{List-manipulation functions}
49 %*                                                      *
50 %*********************************************************
51
52 \begin{code}
53 -- | Extract the first element of a list, which must be non-empty.
54 head                    :: [a] -> a
55 head (x:_)              =  x
56 head []                 =  badHead
57 {-# NOINLINE [1] head #-}
58
59 badHead :: a
60 badHead = errorEmptyList "head"
61
62 -- This rule is useful in cases like
63 --      head [y | (x,y) <- ps, x==t]
64 {-# RULES
65 "head/build"    forall (g::forall b.(a->b->b)->b->b) .
66                 head (build g) = g (\x _ -> x) badHead
67 "head/augment"  forall xs (g::forall b. (a->b->b) -> b -> b) .
68                 head (augment g xs) = g (\x _ -> x) (head xs)
69  #-}
70
71 -- | Decompose a list into its head and tail. If the list is empty,
72 -- returns 'Nothing'. If the list is non-empty, returns @'Just' (x, xs)@,
73 -- where @x@ is the head of the list and @xs@ its tail.
74 --
75 -- /Since: 4.8.0.0/
76 uncons                  :: [a] -> Maybe (a, [a])
77 uncons []               = Nothing
78 uncons (x:xs)           = Just (x, xs)
79
80 -- | Extract the elements after the head of a list, which must be non-empty.
81 tail                    :: [a] -> [a]
82 tail (_:xs)             =  xs
83 tail []                 =  errorEmptyList "tail"
84
85 -- | Extract the last element of a list, which must be finite and non-empty.
86 last                    :: [a] -> a
87 #ifdef USE_REPORT_PRELUDE
88 last [x]                =  x
89 last (_:xs)             =  last xs
90 last []                 =  errorEmptyList "last"
91 #else
92 -- use foldl to allow fusion
93 last = foldl (\_ x -> x) (errorEmptyList "last")
94 #endif
95
96 -- | Return all the elements of a list except the last one.
97 -- The list must be non-empty.
98 init                    :: [a] -> [a]
99 #ifdef USE_REPORT_PRELUDE
100 init [x]                =  []
101 init (x:xs)             =  x : init xs
102 init []                 =  errorEmptyList "init"
103 #else
104 -- eliminate repeated cases
105 init []                 =  errorEmptyList "init"
106 init (x:xs)             =  init' x xs
107   where init' _ []     = []
108         init' y (z:zs) = y : init' z zs
109 #endif
110
111 -- | Test whether a list is empty.
112 null                    :: [a] -> Bool
113 null []                 =  True
114 null (_:_)              =  False
115
116 -- | /O(n)/. 'length' returns the length of a finite list as an 'Int'.
117 -- It is an instance of the more general 'Data.List.genericLength',
118 -- the result type of which may be any kind of number.
119 {-# NOINLINE [1] length #-}
120 length                  :: [a] -> Int
121 length xs               = lenAcc xs 0
122
123 lenAcc          :: [a] -> Int -> Int
124 lenAcc []     n = n
125 lenAcc (_:ys) n = lenAcc ys (n+1)
126
127 {-# RULES
128 "length" [~1] forall xs . length xs = foldr lengthFB idLength xs 0
129 "lengthList" [1] foldr lengthFB idLength = lenAcc
130  #-}
131
132 -- The lambda form turns out to be necessary to make this inline
133 -- when we need it to and give good performance.
134 {-# INLINE [0] lengthFB #-}
135 lengthFB :: x -> (Int -> Int) -> Int -> Int
136 lengthFB _ r = \ !a -> r (a + 1)
137
138 {-# INLINE [0] idLength #-}
139 idLength :: Int -> Int
140 idLength = id
141
142 -- | 'filter', applied to a predicate and a list, returns the list of
143 -- those elements that satisfy the predicate; i.e.,
144 --
145 -- > filter p xs = [ x | x <- xs, p x]
146
147 {-# NOINLINE [1] filter #-}
148 filter :: (a -> Bool) -> [a] -> [a]
149 filter _pred []    = []
150 filter pred (x:xs)
151   | pred x         = x : filter pred xs
152   | otherwise      = filter pred xs
153
154 {-# NOINLINE [0] filterFB #-}
155 filterFB :: (a -> b -> b) -> (a -> Bool) -> a -> b -> b
156 filterFB c p x r | p x       = x `c` r
157                  | otherwise = r
158
159 {-# RULES
160 "filter"     [~1] forall p xs.  filter p xs = build (\c n -> foldr (filterFB c p) n xs)
161 "filterList" [1]  forall p.     foldr (filterFB (:) p) [] = filter p
162 "filterFB"        forall c p q. filterFB (filterFB c p) q = filterFB c (\x -> q x && p x)
163  #-}
164
165 -- Note the filterFB rule, which has p and q the "wrong way round" in the RHS.
166 --     filterFB (filterFB c p) q a b
167 --   = if q a then filterFB c p a b else b
168 --   = if q a then (if p a then c a b else b) else b
169 --   = if q a && p a then c a b else b
170 --   = filterFB c (\x -> q x && p x) a b
171 -- I originally wrote (\x -> p x && q x), which is wrong, and actually
172 -- gave rise to a live bug report.  SLPJ.
173
174
175 -- | 'foldl', applied to a binary operator, a starting value (typically
176 -- the left-identity of the operator), and a list, reduces the list
177 -- using the binary operator, from left to right:
178 --
179 -- > foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
180 --
181 -- The list must be finite.
182
183 -- We write foldl as a non-recursive thing, so that it
184 -- can be inlined, and then (often) strictness-analysed,
185 -- and hence the classic space leak on foldl (+) 0 xs
186
187 foldl :: forall a b. (b -> a -> b) -> b -> [a] -> b
188 {-# INLINE foldl #-}
189 foldl k z0 xs =
190   foldr (\(v::a) (fn::b->b) -> oneShot (\(z::b) -> fn (k z v))) (id :: b -> b) xs z0
191   -- See Note [Left folds via right fold]
192
193 {-
194 Note [Left folds via right fold]
195
196 Implementing foldl et. al. via foldr is only a good idea if the compiler can
197 optimize the resulting code (eta-expand the recursive "go"). See #7994.
198 We hope that one of the two measure kick in:
199
200    * Call Arity (-fcall-arity, enabled by default) eta-expands it if it can see
201      all calls and determine that the arity is large.
202    * The oneShot annotation gives a hint to the regular arity analysis that
203      it may assume that the lambda is called at most once.
204      See [One-shot lambdas] in CoreArity and especially [Eta expanding thunks]
205      in CoreArity.
206
207 The oneShot annotations used in this module are correct, as we only use them in
208 argumets to foldr, where we know how the arguments are called.
209 -}
210
211 -- ----------------------------------------------------------------------------
212
213 -- | A strict version of 'foldl'.
214 foldl'           :: forall a b . (b -> a -> b) -> b -> [a] -> b
215 {-# INLINE foldl' #-}
216 foldl' k z0 xs =
217   foldr (\(v::a) (fn::b->b) -> oneShot (\(z::b) -> z `seq` fn (k z v))) (id :: b -> b) xs z0
218   -- See Note [Left folds via right fold]
219
220 -- | 'foldl1' is a variant of 'foldl' that has no starting value argument,
221 -- and thus must be applied to non-empty lists.
222 foldl1                  :: (a -> a -> a) -> [a] -> a
223 foldl1 f (x:xs)         =  foldl f x xs
224 foldl1 _ []             =  errorEmptyList "foldl1"
225
226 -- | A strict version of 'foldl1'
227 foldl1'                  :: (a -> a -> a) -> [a] -> a
228 foldl1' f (x:xs)         =  foldl' f x xs
229 foldl1' _ []             =  errorEmptyList "foldl1'"
230
231 -- -----------------------------------------------------------------------------
232 -- List sum and product
233
234 -- | The 'sum' function computes the sum of a finite list of numbers.
235 sum                     :: (Num a) => [a] -> a
236 {-# INLINE sum #-}
237 sum                     =  foldl (+) 0
238
239 -- | The 'product' function computes the product of a finite list of numbers.
240 product                 :: (Num a) => [a] -> a
241 {-# INLINE product #-}
242 product                 =  foldl (*) 1
243
244 -- | 'scanl' is similar to 'foldl', but returns a list of successive
245 -- reduced values from the left:
246 --
247 -- > scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
248 --
249 -- Note that
250 --
251 -- > last (scanl f z xs) == foldl f z xs.
252
253 -- This peculiar arrangement is necessary to prevent scanl being rewritten in
254 -- its own right-hand side.
255 {-# NOINLINE [1] scanl #-}
256 scanl                   :: (b -> a -> b) -> b -> [a] -> [b]
257 scanl                   = scanlGo
258   where
259     scanlGo           :: (b -> a -> b) -> b -> [a] -> [b]
260     scanlGo f q ls    = q : (case ls of
261                                []   -> []
262                                x:xs -> scanlGo f (f q x) xs)
263
264 -- Note [scanl rewrite rules]
265 {-# RULES
266 "scanl"  [~1] forall f a bs . scanl f a bs =
267   build (\c n -> a `c` foldr (scanlFB f c) (constScanl n) bs a)
268 "scanlList" [1] forall f (a::a) bs .
269     foldr (scanlFB f (:)) (constScanl []) bs a = tail (scanl f a bs)
270  #-}
271
272 {-# INLINE [0] scanlFB #-}
273 scanlFB :: (b -> a -> b) -> (b -> c -> c) -> a -> (b -> c) -> b -> c
274 scanlFB f c = \b g -> oneShot (\x -> let b' = f x b in b' `c` g b')
275   -- See Note [Left folds via right fold]
276
277 {-# INLINE [0] constScanl #-}
278 constScanl :: a -> b -> a
279 constScanl = const
280
281
282 -- | 'scanl1' is a variant of 'scanl' that has no starting value argument:
283 --
284 -- > scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
285
286 scanl1                  :: (a -> a -> a) -> [a] -> [a]
287 scanl1 f (x:xs)         =  scanl f x xs
288 scanl1 _ []             =  []
289
290 -- | A strictly accumulating version of 'scanl'
291 {-# NOINLINE [1] scanl' #-}
292 scanl'           :: (b -> a -> b) -> b -> [a] -> [b]
293 -- This peculiar form is needed to prevent scanl' from being rewritten
294 -- in its own right hand side.
295 scanl' = scanlGo'
296   where
297     scanlGo'           :: (b -> a -> b) -> b -> [a] -> [b]
298     scanlGo' f !q ls    = q : (case ls of
299                             []   -> []
300                             x:xs -> scanlGo' f (f q x) xs)
301
302 -- Note [scanl rewrite rules]
303 {-# RULES
304 "scanl'"  [~1] forall f a bs . scanl' f a bs =
305   build (\c n -> a `c` foldr (scanlFB' f c) (flipSeqScanl' n) bs a)
306 "scanlList'" [1] forall f a bs .
307     foldr (scanlFB' f (:)) (flipSeqScanl' []) bs a = tail (scanl' f a bs)
308  #-}
309
310 {-# INLINE [0] scanlFB' #-}
311 scanlFB' :: (b -> a -> b) -> (b -> c -> c) -> a -> (b -> c) -> b -> c
312 scanlFB' f c = \b g -> oneShot (\x -> let !b' = f x b in b' `c` g b')
313   -- See Note [Left folds via right fold]
314
315 {-# INLINE [0] flipSeqScanl' #-}
316 flipSeqScanl' :: a -> b -> a
317 flipSeqScanl' a !_b = a
318
319 {-
320 Note [scanl rewrite rules]
321 ~~~~~~~~~~~~~~~~~~~~~~~~~~
322
323 In most cases, when we rewrite a form to one that can fuse, we try to rewrite it
324 back to the original form if it does not fuse. For scanl, we do something a
325 little different. In particular, we rewrite
326
327 scanl f a bs
328
329 to
330
331 build (\c n -> a `c` foldr (scanlFB f c) (constScanl n) bs a)
332
333 When build is inlined, this becomes
334
335 a : foldr (scanlFB f (:)) (constScanl []) bs a
336
337 To rewrite this form back to scanl, we would need a rule that looked like
338
339 forall f a bs. a : foldr (scanlFB f (:)) (constScanl []) bs a = scanl f a bs
340
341 The problem with this rule is that it has (:) at its head. This would have the
342 effect of changing the way the inliner looks at (:), not only here but
343 everywhere.  In most cases, this makes no difference, but in some cases it
344 causes it to come to a different decision about whether to inline something.
345 Based on nofib benchmarks, this is bad for performance. Therefore, we instead
346 match on everything past the :, which is just the tail of scanl.
347 -}
348
349 -- foldr, foldr1, scanr, and scanr1 are the right-to-left duals of the
350 -- above functions.
351
352 -- | 'foldr1' is a variant of 'foldr' that has no starting value argument,
353 -- and thus must be applied to non-empty lists.
354
355 foldr1                  :: (a -> a -> a) -> [a] -> a
356 foldr1 _ [x]            =  x
357 foldr1 f (x:xs)         =  f x (foldr1 f xs)
358 foldr1 _ []             =  errorEmptyList "foldr1"
359
360 -- | 'scanr' is the right-to-left dual of 'scanl'.
361 -- Note that
362 --
363 -- > head (scanr f z xs) == foldr f z xs.
364 {-# NOINLINE [1] scanr #-}
365 scanr                   :: (a -> b -> b) -> b -> [a] -> [b]
366 scanr _ q0 []           =  [q0]
367 scanr f q0 (x:xs)       =  f x q : qs
368                            where qs@(q:_) = scanr f q0 xs
369
370 {-# INLINE [0] strictUncurryScanr #-}
371 strictUncurryScanr :: (a -> b -> c) -> (a, b) -> c
372 strictUncurryScanr f pair = case pair of
373                               (x, y) -> f x y
374
375 {-# INLINE [0] scanrFB #-}
376 scanrFB :: (a -> b -> b) -> (b -> c -> c) -> a -> (b, c) -> (b, c)
377 scanrFB f c = \x (r, est) -> (f x r, r `c` est)
378
379 {-# RULES
380 "scanr" [~1] forall f q0 ls . scanr f q0 ls =
381   build (\c n -> strictUncurryScanr c (foldr (scanrFB f c) (q0,n) ls))
382 "scanrList" [1] forall f q0 ls .
383                strictUncurryScanr (:) (foldr (scanrFB f (:)) (q0,[]) ls) =
384                  scanr f q0 ls
385  #-}
386
387 -- | 'scanr1' is a variant of 'scanr' that has no starting value argument.
388 scanr1                  :: (a -> a -> a) -> [a] -> [a]
389 scanr1 _ []             =  []
390 scanr1 _ [x]            =  [x]
391 scanr1 f (x:xs)         =  f x q : qs
392                            where qs@(q:_) = scanr1 f xs
393
394 -- | 'maximum' returns the maximum value from a list,
395 -- which must be non-empty, finite, and of an ordered type.
396 -- It is a special case of 'Data.List.maximumBy', which allows the
397 -- programmer to supply their own comparison function.
398 maximum                 :: (Ord a) => [a] -> a
399 {-# INLINE [1] maximum #-}
400 maximum []              =  errorEmptyList "maximum"
401 maximum xs              =  foldl1 max xs
402
403 {-# RULES
404   "maximumInt"     maximum = (strictMaximum :: [Int]     -> Int);
405   "maximumInteger" maximum = (strictMaximum :: [Integer] -> Integer)
406  #-}
407
408 -- We can't make the overloaded version of maximum strict without
409 -- changing its semantics (max might not be strict), but we can for
410 -- the version specialised to 'Int'.
411 strictMaximum           :: (Ord a) => [a] -> a
412 strictMaximum []        =  errorEmptyList "maximum"
413 strictMaximum xs        =  foldl1' max xs
414
415 -- | 'minimum' returns the minimum value from a list,
416 -- which must be non-empty, finite, and of an ordered type.
417 -- It is a special case of 'Data.List.minimumBy', which allows the
418 -- programmer to supply their own comparison function.
419 minimum                 :: (Ord a) => [a] -> a
420 {-# INLINE [1] minimum #-}
421 minimum []              =  errorEmptyList "minimum"
422 minimum xs              =  foldl1 min xs
423
424 {-# RULES
425   "minimumInt"     minimum = (strictMinimum :: [Int]     -> Int);
426   "minimumInteger" minimum = (strictMinimum :: [Integer] -> Integer)
427  #-}
428
429 strictMinimum           :: (Ord a) => [a] -> a
430 strictMinimum []        =  errorEmptyList "minimum"
431 strictMinimum xs        =  foldl1' min xs
432
433
434 -- | 'iterate' @f x@ returns an infinite list of repeated applications
435 -- of @f@ to @x@:
436 --
437 -- > iterate f x == [x, f x, f (f x), ...]
438
439 {-# NOINLINE [1] iterate #-}
440 iterate :: (a -> a) -> a -> [a]
441 iterate f x =  x : iterate f (f x)
442
443 {-# NOINLINE [0] iterateFB #-}
444 iterateFB :: (a -> b -> b) -> (a -> a) -> a -> b
445 iterateFB c f x0 = go x0
446   where go x = x `c` go (f x)
447
448 {-# RULES
449 "iterate"    [~1] forall f x.   iterate f x = build (\c _n -> iterateFB c f x)
450 "iterateFB"  [1]                iterateFB (:) = iterate
451  #-}
452
453
454 -- | 'repeat' @x@ is an infinite list, with @x@ the value of every element.
455 repeat :: a -> [a]
456 {-# INLINE [0] repeat #-}
457 -- The pragma just gives the rules more chance to fire
458 repeat x = xs where xs = x : xs
459
460 {-# INLINE [0] repeatFB #-}     -- ditto
461 repeatFB :: (a -> b -> b) -> a -> b
462 repeatFB c x = xs where xs = x `c` xs
463
464
465 {-# RULES
466 "repeat"    [~1] forall x. repeat x = build (\c _n -> repeatFB c x)
467 "repeatFB"  [1]  repeatFB (:)       = repeat
468  #-}
469
470 -- | 'replicate' @n x@ is a list of length @n@ with @x@ the value of
471 -- every element.
472 -- It is an instance of the more general 'Data.List.genericReplicate',
473 -- in which @n@ may be of any integral type.
474 {-# INLINE replicate #-}
475 replicate               :: Int -> a -> [a]
476 replicate n x           =  take n (repeat x)
477
478 -- | 'cycle' ties a finite list into a circular one, or equivalently,
479 -- the infinite repetition of the original list.  It is the identity
480 -- on infinite lists.
481
482 cycle                   :: [a] -> [a]
483 cycle []                = errorEmptyList "cycle"
484 cycle xs                = xs' where xs' = xs ++ xs'
485
486 -- | 'takeWhile', applied to a predicate @p@ and a list @xs@, returns the
487 -- longest prefix (possibly empty) of @xs@ of elements that satisfy @p@:
488 --
489 -- > takeWhile (< 3) [1,2,3,4,1,2,3,4] == [1,2]
490 -- > takeWhile (< 9) [1,2,3] == [1,2,3]
491 -- > takeWhile (< 0) [1,2,3] == []
492 --
493
494 {-# NOINLINE [1] takeWhile #-}
495 takeWhile               :: (a -> Bool) -> [a] -> [a]
496 takeWhile _ []          =  []
497 takeWhile p (x:xs)
498             | p x       =  x : takeWhile p xs
499             | otherwise =  []
500
501 {-# INLINE [0] takeWhileFB #-}
502 takeWhileFB :: (a -> Bool) -> (a -> b -> b) -> b -> a -> b -> b
503 takeWhileFB p c n = \x r -> if p x then x `c` r else n
504
505 -- The takeWhileFB rule is similar to the filterFB rule. It works like this:
506 -- takeWhileFB q (takeWhileFB p c n) n =
507 -- \x r -> if q x then (takeWhileFB p c n) x r else n =
508 -- \x r -> if q x then (\x' r' -> if p x' then x' `c` r' else n) x r else n =
509 -- \x r -> if q x then (if p x then x `c` r else n) else n =
510 -- \x r -> if q x && p x then x `c` r else n =
511 -- takeWhileFB (\x -> q x && p x) c n
512 {-# RULES
513 "takeWhile"     [~1] forall p xs. takeWhile p xs =
514                                 build (\c n -> foldr (takeWhileFB p c n) n xs)
515 "takeWhileList" [1]  forall p.    foldr (takeWhileFB p (:) []) [] = takeWhile p
516 "takeWhileFB"        forall c n p q. takeWhileFB q (takeWhileFB p c n) n =
517                         takeWhileFB (\x -> q x && p x) c n
518  #-}
519
520 -- | 'dropWhile' @p xs@ returns the suffix remaining after 'takeWhile' @p xs@:
521 --
522 -- > dropWhile (< 3) [1,2,3,4,5,1,2,3] == [3,4,5,1,2,3]
523 -- > dropWhile (< 9) [1,2,3] == []
524 -- > dropWhile (< 0) [1,2,3] == [1,2,3]
525 --
526
527 dropWhile               :: (a -> Bool) -> [a] -> [a]
528 dropWhile _ []          =  []
529 dropWhile p xs@(x:xs')
530             | p x       =  dropWhile p xs'
531             | otherwise =  xs
532
533 -- | 'take' @n@, applied to a list @xs@, returns the prefix of @xs@
534 -- of length @n@, or @xs@ itself if @n > 'length' xs@:
535 --
536 -- > take 5 "Hello World!" == "Hello"
537 -- > take 3 [1,2,3,4,5] == [1,2,3]
538 -- > take 3 [1,2] == [1,2]
539 -- > take 3 [] == []
540 -- > take (-1) [1,2] == []
541 -- > take 0 [1,2] == []
542 --
543 -- It is an instance of the more general 'Data.List.genericTake',
544 -- in which @n@ may be of any integral type.
545 take                   :: Int -> [a] -> [a]
546 #ifdef USE_REPORT_PRELUDE
547 take n _      | n <= 0 =  []
548 take _ []              =  []
549 take n (x:xs)          =  x : take (n-1) xs
550 #else
551
552 {- We always want to inline this to take advantage of a known length argument
553 sign. Note, however, that it's important for the RULES to grab take, rather
554 than trying to INLINE take immediately and then letting the RULES grab
555 unsafeTake. Presumably the latter approach doesn't grab it early enough; it led
556 to an allocation regression in nofib/fft2. -}
557 {-# INLINE [1] take #-}
558 take n xs | 0 < n     = unsafeTake n xs
559           | otherwise = []
560
561 -- A version of take that takes the whole list if it's given an argument less
562 -- than 1.
563 {-# NOINLINE [1] unsafeTake #-}
564 unsafeTake :: Int -> [a] -> [a]
565 unsafeTake !_  []     = []
566 unsafeTake 1   (x: _) = [x]
567 unsafeTake m   (x:xs) = x : unsafeTake (m - 1) xs
568
569 {-# RULES
570 "take"     [~1] forall n xs . take n xs =
571   build (\c nil -> if 0 < n
572                    then foldr (takeFB c nil) (flipSeqTake nil) xs n
573                    else nil)
574 "unsafeTakeList"  [1] forall n xs . foldr (takeFB (:) []) (flipSeqTake []) xs n
575                                         = unsafeTake n xs
576  #-}
577
578 {-# INLINE [0] flipSeqTake #-}
579 -- Just flip seq, specialized to Int, but not inlined too early.
580 -- It's important to force the numeric argument here, even though
581 -- it's not used. Otherwise, take n [] doesn't force n. This is
582 -- bad for strictness analysis and unboxing, and leads to increased
583 -- allocation in T7257.
584 flipSeqTake :: a -> Int -> a
585 flipSeqTake x !_n = x
586
587 {-# INLINE [0] takeFB #-}
588 takeFB :: (a -> b -> b) -> b -> a -> (Int -> b) -> Int -> b
589 -- The \m accounts for the fact that takeFB is used in a higher-order
590 -- way by takeFoldr, so it's better to inline.  A good example is
591 --     take n (repeat x)
592 -- for which we get excellent code... but only if we inline takeFB
593 -- when given four arguments
594 takeFB c n x xs
595   = \ m -> case m of
596             1 -> x `c` n
597             _ -> x `c` xs (m - 1)
598 #endif
599
600 -- | 'drop' @n xs@ returns the suffix of @xs@
601 -- after the first @n@ elements, or @[]@ if @n > 'length' xs@:
602 --
603 -- > drop 6 "Hello World!" == "World!"
604 -- > drop 3 [1,2,3,4,5] == [4,5]
605 -- > drop 3 [1,2] == []
606 -- > drop 3 [] == []
607 -- > drop (-1) [1,2] == [1,2]
608 -- > drop 0 [1,2] == [1,2]
609 --
610 -- It is an instance of the more general 'Data.List.genericDrop',
611 -- in which @n@ may be of any integral type.
612 drop                   :: Int -> [a] -> [a]
613 #ifdef USE_REPORT_PRELUDE
614 drop n xs     | n <= 0 =  xs
615 drop _ []              =  []
616 drop n (_:xs)          =  drop (n-1) xs
617 #else /* hack away */
618 {-# INLINE drop #-}
619 drop n ls
620   | n <= 0     = ls
621   | otherwise  = unsafeDrop n ls
622   where
623     -- A version of drop that drops the whole list if given an argument
624     -- less than 1
625     unsafeDrop :: Int -> [a] -> [a]
626     unsafeDrop !_ []     = []
627     unsafeDrop 1  (_:xs) = xs
628     unsafeDrop m  (_:xs) = unsafeDrop (m - 1) xs
629 #endif
630
631 -- | 'splitAt' @n xs@ returns a tuple where first element is @xs@ prefix of
632 -- length @n@ and second element is the remainder of the list:
633 --
634 -- > splitAt 6 "Hello World!" == ("Hello ","World!")
635 -- > splitAt 3 [1,2,3,4,5] == ([1,2,3],[4,5])
636 -- > splitAt 1 [1,2,3] == ([1],[2,3])
637 -- > splitAt 3 [1,2,3] == ([1,2,3],[])
638 -- > splitAt 4 [1,2,3] == ([1,2,3],[])
639 -- > splitAt 0 [1,2,3] == ([],[1,2,3])
640 -- > splitAt (-1) [1,2,3] == ([],[1,2,3])
641 --
642 -- It is equivalent to @('take' n xs, 'drop' n xs)@ when @n@ is not @_|_@
643 -- (@splitAt _|_ xs = _|_@).
644 -- 'splitAt' is an instance of the more general 'Data.List.genericSplitAt',
645 -- in which @n@ may be of any integral type.
646 splitAt                :: Int -> [a] -> ([a],[a])
647
648 #ifdef USE_REPORT_PRELUDE
649 splitAt n xs           =  (take n xs, drop n xs)
650 #else
651 splitAt n ls
652   | n <= 0 = ([], ls)
653   | otherwise          = splitAt' n ls
654     where
655         splitAt' :: Int -> [a] -> ([a], [a])
656         splitAt' _  []     = ([], [])
657         splitAt' 1  (x:xs) = ([x], xs)
658         splitAt' m  (x:xs) = (x:xs', xs'')
659           where
660             (xs', xs'') = splitAt' (m - 1) xs
661 #endif /* USE_REPORT_PRELUDE */
662
663 -- | 'span', applied to a predicate @p@ and a list @xs@, returns a tuple where
664 -- first element is longest prefix (possibly empty) of @xs@ of elements that
665 -- satisfy @p@ and second element is the remainder of the list:
666 --
667 -- > span (< 3) [1,2,3,4,1,2,3,4] == ([1,2],[3,4,1,2,3,4])
668 -- > span (< 9) [1,2,3] == ([1,2,3],[])
669 -- > span (< 0) [1,2,3] == ([],[1,2,3])
670 --
671 -- 'span' @p xs@ is equivalent to @('takeWhile' p xs, 'dropWhile' p xs)@
672
673 span                    :: (a -> Bool) -> [a] -> ([a],[a])
674 span _ xs@[]            =  (xs, xs)
675 span p xs@(x:xs')
676          | p x          =  let (ys,zs) = span p xs' in (x:ys,zs)
677          | otherwise    =  ([],xs)
678
679 -- | 'break', applied to a predicate @p@ and a list @xs@, returns a tuple where
680 -- first element is longest prefix (possibly empty) of @xs@ of elements that
681 -- /do not satisfy/ @p@ and second element is the remainder of the list:
682 --
683 -- > break (> 3) [1,2,3,4,1,2,3,4] == ([1,2,3],[4,1,2,3,4])
684 -- > break (< 9) [1,2,3] == ([],[1,2,3])
685 -- > break (> 9) [1,2,3] == ([1,2,3],[])
686 --
687 -- 'break' @p@ is equivalent to @'span' ('not' . p)@.
688
689 break                   :: (a -> Bool) -> [a] -> ([a],[a])
690 #ifdef USE_REPORT_PRELUDE
691 break p                 =  span (not . p)
692 #else
693 -- HBC version (stolen)
694 break _ xs@[]           =  (xs, xs)
695 break p xs@(x:xs')
696            | p x        =  ([],xs)
697            | otherwise  =  let (ys,zs) = break p xs' in (x:ys,zs)
698 #endif
699
700 -- | 'reverse' @xs@ returns the elements of @xs@ in reverse order.
701 -- @xs@ must be finite.
702 reverse                 :: [a] -> [a]
703 #ifdef USE_REPORT_PRELUDE
704 reverse                 =  foldl (flip (:)) []
705 #else
706 reverse l =  rev l []
707   where
708     rev []     a = a
709     rev (x:xs) a = rev xs (x:a)
710 #endif
711
712 -- | 'and' returns the conjunction of a Boolean list.  For the result to be
713 -- 'True', the list must be finite; 'False', however, results from a 'False'
714 -- value at a finite index of a finite or infinite list.
715 and                     :: [Bool] -> Bool
716 #ifdef USE_REPORT_PRELUDE
717 and                     =  foldr (&&) True
718 #else
719 and []          =  True
720 and (x:xs)      =  x && and xs
721 {-# NOINLINE [1] and #-}
722
723 {-# RULES
724 "and/build"     forall (g::forall b.(Bool->b->b)->b->b) .
725                 and (build g) = g (&&) True
726  #-}
727 #endif
728
729 -- | 'or' returns the disjunction of a Boolean list.  For the result to be
730 -- 'False', the list must be finite; 'True', however, results from a 'True'
731 -- value at a finite index of a finite or infinite list.
732 or                      :: [Bool] -> Bool
733 #ifdef USE_REPORT_PRELUDE
734 or                      =  foldr (||) False
735 #else
736 or []           =  False
737 or (x:xs)       =  x || or xs
738 {-# NOINLINE [1] or #-}
739
740 {-# RULES
741 "or/build"      forall (g::forall b.(Bool->b->b)->b->b) .
742                 or (build g) = g (||) False
743  #-}
744 #endif
745
746 -- | Applied to a predicate and a list, 'any' determines if any element
747 -- of the list satisfies the predicate.  For the result to be
748 -- 'False', the list must be finite; 'True', however, results from a 'True'
749 -- value for the predicate applied to an element at a finite index of a finite or infinite list.
750 any                     :: (a -> Bool) -> [a] -> Bool
751
752 #ifdef USE_REPORT_PRELUDE
753 any p                   =  or . map p
754 #else
755 any _ []        = False
756 any p (x:xs)    = p x || any p xs
757
758 {-# NOINLINE [1] any #-}
759
760 {-# RULES
761 "any/build"     forall p (g::forall b.(a->b->b)->b->b) .
762                 any p (build g) = g ((||) . p) False
763  #-}
764 #endif
765
766 -- | Applied to a predicate and a list, 'all' determines if all elements
767 -- of the list satisfy the predicate. For the result to be
768 -- 'True', the list must be finite; 'False', however, results from a 'False'
769 -- value for the predicate applied to an element at a finite index of a finite or infinite list.
770 all                     :: (a -> Bool) -> [a] -> Bool
771 #ifdef USE_REPORT_PRELUDE
772 all p                   =  and . map p
773 #else
774 all _ []        =  True
775 all p (x:xs)    =  p x && all p xs
776
777 {-# NOINLINE [1] all #-}
778
779 {-# RULES
780 "all/build"     forall p (g::forall b.(a->b->b)->b->b) .
781                 all p (build g) = g ((&&) . p) True
782  #-}
783 #endif
784
785 -- | 'elem' is the list membership predicate, usually written in infix form,
786 -- e.g., @x \`elem\` xs@.  For the result to be
787 -- 'False', the list must be finite; 'True', however, results from an element
788 -- equal to @x@ found at a finite index of a finite or infinite list.
789 elem                    :: (Eq a) => a -> [a] -> Bool
790 #ifdef USE_REPORT_PRELUDE
791 elem x                  =  any (== x)
792 #else
793 elem _ []       = False
794 elem x (y:ys)   = x==y || elem x ys
795 {-# NOINLINE [1] elem #-}
796 {-# RULES
797 "elem/build"    forall x (g :: forall b . Eq a => (a -> b -> b) -> b -> b)
798    . elem x (build g) = g (\ y r -> (x == y) || r) False
799  #-}
800 #endif
801
802 -- | 'notElem' is the negation of 'elem'.
803 notElem                 :: (Eq a) => a -> [a] -> Bool
804 #ifdef USE_REPORT_PRELUDE
805 notElem x               =  all (/= x)
806 #else
807 notElem _ []    =  True
808 notElem x (y:ys)=  x /= y && notElem x ys
809 {-# NOINLINE [1] notElem #-}
810 {-# RULES
811 "notElem/build" forall x (g :: forall b . Eq a => (a -> b -> b) -> b -> b)
812    . notElem x (build g) = g (\ y r -> (x /= y) && r) True
813  #-}
814 #endif
815
816 -- | 'lookup' @key assocs@ looks up a key in an association list.
817 lookup                  :: (Eq a) => a -> [(a,b)] -> Maybe b
818 lookup _key []          =  Nothing
819 lookup  key ((x,y):xys)
820     | key == x          =  Just y
821     | otherwise         =  lookup key xys
822
823 -- | Map a function over a list and concatenate the results.
824 concatMap               :: (a -> [b]) -> [a] -> [b]
825 concatMap f             =  foldr ((++) . f) []
826
827 {-# NOINLINE [1] concatMap #-}
828
829 {-# RULES
830 "concatMap" forall f xs . concatMap f xs =
831     build (\c n -> foldr (\x b -> foldr c b (f x)) n xs)
832  #-}
833
834
835 -- | Concatenate a list of lists.
836 concat :: [[a]] -> [a]
837 concat = foldr (++) []
838
839 {-# NOINLINE [1] concat #-}
840
841 {-# RULES
842   "concat" forall xs. concat xs =
843      build (\c n -> foldr (\x y -> foldr c y x) n xs)
844 -- We don't bother to turn non-fusible applications of concat back into concat
845  #-}
846
847 \end{code}
848
849
850 \begin{code}
851 -- | List index (subscript) operator, starting from 0.
852 -- It is an instance of the more general 'Data.List.genericIndex',
853 -- which takes an index of any integral type.
854 (!!)                    :: [a] -> Int -> a
855 #ifdef USE_REPORT_PRELUDE
856 xs     !! n | n < 0 =  error "Prelude.!!: negative index"
857 []     !! _         =  error "Prelude.!!: index too large"
858 (x:_)  !! 0         =  x
859 (_:xs) !! n         =  xs !! (n-1)
860 #else
861
862 -- We don't really want the errors to inline with (!!).
863 -- We may want to fuss around a bit with NOINLINE, and
864 -- if so we should be careful not to trip up known-bottom
865 -- optimizations.
866 tooLarge :: Int -> a
867 tooLarge _ = error (prel_list_str ++ "!!: index too large")
868
869 negIndex :: a
870 negIndex = error $ prel_list_str ++ "!!: negative index"
871
872 {-# INLINABLE (!!) #-}
873 xs !! n
874   | n < 0     = negIndex
875   | otherwise = foldr (\x r k -> case k of
876                                    0 -> x
877                                    _ -> r (k-1)) tooLarge xs n
878 #endif
879 \end{code}
880
881
882 %*********************************************************
883 %*                                                      *
884 \subsection{The zip family}
885 %*                                                      *
886 %*********************************************************
887
888 \begin{code}
889 foldr2 :: (a -> b -> c -> c) -> c -> [a] -> [b] -> c
890 foldr2 k z = go
891   where
892         go []    !_ys    = z -- see #9495 for the !
893         go _xs   []      = z
894         go (x:xs) (y:ys) = k x y (go xs ys)
895 {-# INLINE [0] foldr2 #-}
896
897 foldr2_left :: (a -> b -> c -> d) -> d -> a -> ([b] -> c) -> [b] -> d
898 foldr2_left _k  z _x _r []     = z
899 foldr2_left  k _z  x  r (y:ys) = k x y (r ys)
900
901 foldr2_right :: (a -> b -> c -> d) -> d -> b -> ([a] -> c) -> [a] -> d
902 foldr2_right _k z  _y _r []     = z
903 foldr2_right  k _z  y  r (x:xs) = k x y (r xs)
904
905 -- foldr2 k z xs ys = foldr (foldr2_left k z)  (\_ -> z) xs ys
906 -- foldr2 k z xs ys = foldr (foldr2_right k z) (\_ -> z) ys xs
907 {-# RULES
908 "foldr2/left"   forall k z ys (g::forall b.(a->b->b)->b->b) .
909                   foldr2 k z (build g) ys = g (foldr2_left  k z) (\_ -> z) ys
910
911 "foldr2/right"  forall k z xs (g::forall b.(a->b->b)->b->b) .
912                   foldr2 k z xs (build g) = g (foldr2_right k z) (\_ -> z) xs
913  #-}
914 \end{code}
915
916 Zips for larger tuples are in the List module.
917
918 \begin{code}
919 ----------------------------------------------
920 -- | 'zip' takes two lists and returns a list of corresponding pairs.
921 -- If one input list is short, excess elements of the longer list are
922 -- discarded.
923 --
924 -- NOTE: GHC's implementation of @zip@ deviates slightly from the
925 -- standard. In particular, Haskell 98 and Haskell 2010 require that
926 -- @zip [x1,x2,...,xn] (y1:y2:...:yn:_|_) = [(x1,y1),(x2,y2),...,(xn,yn)]@
927 -- In GHC, however,
928 -- @zip [x1,x2,...,xn] (y1:y2:...:yn:_|_) = (x1,y1):(x2,y2):...:(xn,yn):_|_@
929 -- That is, you cannot use termination of the left list to avoid hitting
930 -- bottom in the right list.
931
932 -- This deviation is necessary to make fusion with 'build' in the right
933 -- list preserve semantics.
934 {-# NOINLINE [1] zip #-}
935 zip :: [a] -> [b] -> [(a,b)]
936 zip []     !_bs   = [] -- see #9495 for the !
937 zip _as    []     = []
938 zip (a:as) (b:bs) = (a,b) : zip as bs
939
940 {-# INLINE [0] zipFB #-}
941 zipFB :: ((a, b) -> c -> d) -> a -> b -> c -> d
942 zipFB c = \x y r -> (x,y) `c` r
943
944 {-# RULES
945 "zip"      [~1] forall xs ys. zip xs ys = build (\c n -> foldr2 (zipFB c) n xs ys)
946 "zipList"  [1]  foldr2 (zipFB (:)) []   = zip
947  #-}
948 \end{code}
949
950 \begin{code}
951 ----------------------------------------------
952 -- | 'zip3' takes three lists and returns a list of triples, analogous to
953 -- 'zip'.
954 zip3 :: [a] -> [b] -> [c] -> [(a,b,c)]
955 -- Specification
956 -- zip3 =  zipWith3 (,,)
957 zip3 (a:as) (b:bs) (c:cs) = (a,b,c) : zip3 as bs cs
958 zip3 _      _      _      = []
959 \end{code}
960
961
962 -- The zipWith family generalises the zip family by zipping with the
963 -- function given as the first argument, instead of a tupling function.
964
965 \begin{code}
966 ----------------------------------------------
967 -- | 'zipWith' generalises 'zip' by zipping with the function given
968 -- as the first argument, instead of a tupling function.
969 -- For example, @'zipWith' (+)@ is applied to two lists to produce the
970 -- list of corresponding sums.
971 --
972 -- NOTE: GHC's implementation of @zipWith@ deviates slightly from the
973 -- standard. In particular, Haskell 98 and Haskell 2010 require that
974 -- @zipWith (,) [x1,x2,...,xn] (y1:y2:...:yn:_|_) = [(x1,y1),(x2,y2),...,(xn,yn)]@
975 -- In GHC, however,
976 -- @zipWith (,) [x1,x2,...,xn] (y1:y2:...:yn:_|_) = (x1,y1):(x2,y2):...:(xn,yn):_|_@
977 -- That is, you cannot use termination of the left list to avoid hitting
978 -- bottom in the right list.
979
980 -- This deviation is necessary to make fusion with 'build' in the right
981 -- list preserve semantics.
982
983 {-# NOINLINE [1] zipWith #-}
984 zipWith :: (a->b->c) -> [a]->[b]->[c]
985 zipWith _f []     !_bs   = [] -- see #9495 for the !
986 zipWith _f _as    []     = []
987 zipWith f  (a:as) (b:bs) = f a b : zipWith f as bs
988
989 -- zipWithFB must have arity 2 since it gets two arguments in the "zipWith"
990 -- rule; it might not get inlined otherwise
991 {-# INLINE [0] zipWithFB #-}
992 zipWithFB :: (a -> b -> c) -> (d -> e -> a) -> d -> e -> b -> c
993 zipWithFB c f = \x y r -> (x `f` y) `c` r
994
995 {-# RULES
996 "zipWith"       [~1] forall f xs ys.    zipWith f xs ys = build (\c n -> foldr2 (zipWithFB c f) n xs ys)
997 "zipWithList"   [1]  forall f.  foldr2 (zipWithFB (:) f) [] = zipWith f
998   #-}
999 \end{code}
1000
1001 \begin{code}
1002 -- | The 'zipWith3' function takes a function which combines three
1003 -- elements, as well as three lists and returns a list of their point-wise
1004 -- combination, analogous to 'zipWith'.
1005 zipWith3                :: (a->b->c->d) -> [a]->[b]->[c]->[d]
1006 zipWith3 z (a:as) (b:bs) (c:cs)
1007                         =  z a b c : zipWith3 z as bs cs
1008 zipWith3 _ _ _ _        =  []
1009
1010 -- | 'unzip' transforms a list of pairs into a list of first components
1011 -- and a list of second components.
1012 unzip    :: [(a,b)] -> ([a],[b])
1013 {-# INLINE unzip #-}
1014 unzip    =  foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
1015
1016 -- | The 'unzip3' function takes a list of triples and returns three
1017 -- lists, analogous to 'unzip'.
1018 unzip3   :: [(a,b,c)] -> ([a],[b],[c])
1019 {-# INLINE unzip3 #-}
1020 unzip3   =  foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
1021                   ([],[],[])
1022 \end{code}
1023
1024
1025 %*********************************************************
1026 %*                                                      *
1027 \subsection{Error code}
1028 %*                                                      *
1029 %*********************************************************
1030
1031 Common up near identical calls to `error' to reduce the number
1032 constant strings created when compiled:
1033
1034 \begin{code}
1035 errorEmptyList :: String -> a
1036 errorEmptyList fun =
1037   error (prel_list_str ++ fun ++ ": empty list")
1038
1039 prel_list_str :: String
1040 prel_list_str = "Prelude."
1041 \end{code}