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