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