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