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