List.hs 33.9 KB
Newer Older
1
{-# LANGUAGE Trustworthy #-}
Joachim Breitner's avatar
Joachim Breitner committed
2
{-# LANGUAGE CPP, NoImplicitPrelude, ScopedTypeVariables, MagicHash #-}
3
{-# LANGUAGE BangPatterns #-}
4
{-# OPTIONS_HADDOCK hide #-}
5

6 7 8 9 10
-----------------------------------------------------------------------------
-- |
-- Module      :  GHC.List
-- Copyright   :  (c) The University of Glasgow 1994-2002
-- License     :  see libraries/base/LICENSE
Jan Stolarek's avatar
Jan Stolarek committed
11
--
12 13 14 15 16 17 18
-- Maintainer  :  cvs-ghc@haskell.org
-- Stability   :  internal
-- Portability :  non-portable (GHC Extensions)
--
-- The List data type and its operations
--
-----------------------------------------------------------------------------
19 20

module GHC.List (
21
   -- [] (..),          -- built-in syntax; can't be used in export list
22 23

   map, (++), filter, concat,
David Feuer's avatar
David Feuer committed
24
   head, last, tail, init, uncons, null, length, (!!),
25 26 27 28
   foldl, foldl', foldl1, foldl1', scanl, scanl1, scanl', foldr, foldr1,
   scanr, scanr1, iterate, repeat, replicate, cycle,
   take, drop, sum, product, maximum, minimum, splitAt, takeWhile, dropWhile,
   span, break, reverse, and, or,
29
   any, all, elem, notElem, lookup,
30
   concatMap,
31
   zip, zip3, zipWith, zipWith3, unzip, unzip3,
32
   errorEmptyList,
33 34 35

 ) where

36
import Data.Maybe
37
import GHC.Base
38 39
import GHC.Num (Num(..))
import GHC.Integer (Integer)
40 41 42 43

infixl 9  !!
infix  4 `elem`, `notElem`

44 45 46
--------------------------------------------------------------
-- List-manipulation functions
--------------------------------------------------------------
47

ross's avatar
ross committed
48
-- | Extract the first element of a list, which must be non-empty.
49 50 51
head                    :: [a] -> a
head (x:_)              =  x
head []                 =  badHead
52
{-# NOINLINE [1] head #-}
53

Ian Lynagh's avatar
Ian Lynagh committed
54
badHead :: a
55 56
badHead = errorEmptyList "head"

Jan Stolarek's avatar
Jan Stolarek committed
57
-- This rule is useful in cases like
Don Stewart's avatar
Don Stewart committed
58
--      head [y | (x,y) <- ps, x==t]
59
{-# RULES
Don Stewart's avatar
Don Stewart committed
60 61
"head/build"    forall (g::forall b.(a->b->b)->b->b) .
                head (build g) = g (\x _ -> x) badHead
Jan Stolarek's avatar
Jan Stolarek committed
62
"head/augment"  forall xs (g::forall b. (a->b->b) -> b -> b) .
Don Stewart's avatar
Don Stewart committed
63
                head (augment g xs) = g (\x _ -> x) (head xs)
64 65
 #-}

David Feuer's avatar
David Feuer committed
66 67 68
-- | Decompose a list into its head and tail. If the list is empty,
-- returns 'Nothing'. If the list is non-empty, returns @'Just' (x, xs)@,
-- where @x@ is the head of the list and @xs@ its tail.
69
--
70
-- @since 4.8.0.0
David Feuer's avatar
David Feuer committed
71 72 73 74
uncons                  :: [a] -> Maybe (a, [a])
uncons []               = Nothing
uncons (x:xs)           = Just (x, xs)

ross's avatar
ross committed
75
-- | Extract the elements after the head of a list, which must be non-empty.
76 77 78 79
tail                    :: [a] -> [a]
tail (_:xs)             =  xs
tail []                 =  errorEmptyList "tail"

ross's avatar
ross committed
80
-- | Extract the last element of a list, which must be finite and non-empty.
81 82 83 84 85 86
last                    :: [a] -> a
#ifdef USE_REPORT_PRELUDE
last [x]                =  x
last (_:xs)             =  last xs
last []                 =  errorEmptyList "last"
#else
87 88 89 90 91 92 93 94 95
-- Use foldl to make last a good consumer.
-- This will compile to good code for the actual GHC.List.last.
-- (At least as long it is eta-expaned, otherwise it does not, #10260.)
last xs = foldl (\_ x -> x) lastError xs
{-# INLINE last #-}
-- The inline pragma is required to make GHC remember the implementation via
-- foldl.
lastError :: a
lastError = errorEmptyList "last"
96 97
#endif

ross's avatar
ross committed
98
-- | Return all the elements of a list except the last one.
99
-- The list must be non-empty.
100 101 102 103 104 105 106 107 108 109
init                    :: [a] -> [a]
#ifdef USE_REPORT_PRELUDE
init [x]                =  []
init (x:xs)             =  x : init xs
init []                 =  errorEmptyList "init"
#else
-- eliminate repeated cases
init []                 =  errorEmptyList "init"
init (x:xs)             =  init' x xs
  where init' _ []     = []
Don Stewart's avatar
Don Stewart committed
110
        init' y (z:zs) = y : init' z zs
111 112
#endif

ross's avatar
ross committed
113
-- | Test whether a list is empty.
114 115 116 117
null                    :: [a] -> Bool
null []                 =  True
null (_:_)              =  False

118
-- | /O(n)/. 'length' returns the length of a finite list as an 'Int'.
ross's avatar
ross committed
119 120
-- It is an instance of the more general 'Data.List.genericLength',
-- 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 126 127
lenAcc          :: [a] -> Int -> Int
lenAcc []     n = n
lenAcc (_:ys) n = lenAcc ys (n+1)
128 129

{-# RULES
130 131
"length" [~1] forall xs . length xs = foldr lengthFB idLength xs 0
"lengthList" [1] foldr lengthFB idLength = lenAcc
132
 #-}
133

134 135 136 137
-- The lambda form turns out to be necessary to make this inline
-- when we need it to and give good performance.
{-# INLINE [0] lengthFB #-}
lengthFB :: x -> (Int -> Int) -> Int -> Int
138
lengthFB _ r = \ !a -> r (a + 1)
139 140 141 142 143

{-# INLINE [0] idLength #-}
idLength :: Int -> Int
idLength = id

ross's avatar
ross committed
144 145 146 147 148
-- | 'filter', applied to a predicate and a list, returns the list of
-- those elements that satisfy the predicate; i.e.,
--
-- > filter p xs = [ x | x <- xs, p x]

149
{-# NOINLINE [1] filter #-}
150
filter :: (a -> Bool) -> [a] -> [a]
151 152 153
filter _pred []    = []
filter pred (x:xs)
  | pred x         = x : filter pred xs
Don Stewart's avatar
Don Stewart committed
154
  | otherwise      = filter pred xs
155

156
{-# NOINLINE [0] filterFB #-}
Ian Lynagh's avatar
Ian Lynagh committed
157
filterFB :: (a -> b -> b) -> (a -> Bool) -> a -> b -> b
158
filterFB c p x r | p x       = x `c` r
Don Stewart's avatar
Don Stewart committed
159
                 | otherwise = r
160 161

{-# RULES
162
"filter"     [~1] forall p xs.  filter p xs = build (\c n -> foldr (filterFB c p) n xs)
Don Stewart's avatar
Don Stewart committed
163 164
"filterList" [1]  forall p.     foldr (filterFB (:) p) [] = filter p
"filterFB"        forall c p q. filterFB (filterFB c p) q = filterFB c (\x -> q x && p x)
165 166 167 168 169 170 171 172 173 174 175 176
 #-}

-- Note the filterFB rule, which has p and q the "wrong way round" in the RHS.
--     filterFB (filterFB c p) q a b
--   = if q a then filterFB c p a b else b
--   = if q a then (if p a then c a b else b) else b
--   = if q a && p a then c a b else b
--   = filterFB c (\x -> q x && p x) a b
-- I originally wrote (\x -> p x && q x), which is wrong, and actually
-- gave rise to a live bug report.  SLPJ.


ross's avatar
ross committed
177 178 179 180 181 182 183
-- | 'foldl', applied to a binary operator, a starting value (typically
-- the left-identity of the operator), and a list, reduces the list
-- using the binary operator, from left to right:
--
-- > foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
--
-- The list must be finite.
184 185 186 187 188

-- We write foldl as a non-recursive thing, so that it
-- can be inlined, and then (often) strictness-analysed,
-- and hence the classic space leak on foldl (+) 0 xs

Joachim Breitner's avatar
Joachim Breitner committed
189 190
foldl :: forall a b. (b -> a -> b) -> b -> [a] -> b
{-# INLINE foldl #-}
191
foldl k z0 xs =
192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211
  foldr (\(v::a) (fn::b->b) -> oneShot (\(z::b) -> fn (k z v))) (id :: b -> b) xs z0
  -- See Note [Left folds via right fold]

{-
Note [Left folds via right fold]

Implementing foldl et. al. via foldr is only a good idea if the compiler can
optimize the resulting code (eta-expand the recursive "go"). See #7994.
We hope that one of the two measure kick in:

   * Call Arity (-fcall-arity, enabled by default) eta-expands it if it can see
     all calls and determine that the arity is large.
   * The oneShot annotation gives a hint to the regular arity analysis that
     it may assume that the lambda is called at most once.
     See [One-shot lambdas] in CoreArity and especially [Eta expanding thunks]
     in CoreArity.

The oneShot annotations used in this module are correct, as we only use them in
argumets to foldr, where we know how the arguments are called.
-}
212 213 214 215 216 217 218

-- ----------------------------------------------------------------------------

-- | A strict version of 'foldl'.
foldl'           :: forall a b . (b -> a -> b) -> b -> [a] -> b
{-# INLINE foldl' #-}
foldl' k z0 xs =
219 220
  foldr (\(v::a) (fn::b->b) -> oneShot (\(z::b) -> z `seq` fn (k z v))) (id :: b -> b) xs z0
  -- See Note [Left folds via right fold]
221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244

-- | 'foldl1' is a variant of 'foldl' that has no starting value argument,
-- and thus must be applied to non-empty lists.
foldl1                  :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs)         =  foldl f x xs
foldl1 _ []             =  errorEmptyList "foldl1"

-- | A strict version of 'foldl1'
foldl1'                  :: (a -> a -> a) -> [a] -> a
foldl1' f (x:xs)         =  foldl' f x xs
foldl1' _ []             =  errorEmptyList "foldl1'"

-- -----------------------------------------------------------------------------
-- List sum and product

-- | The 'sum' function computes the sum of a finite list of numbers.
sum                     :: (Num a) => [a] -> a
{-# INLINE sum #-}
sum                     =  foldl (+) 0

-- | The 'product' function computes the product of a finite list of numbers.
product                 :: (Num a) => [a] -> a
{-# INLINE product #-}
product                 =  foldl (*) 1
245

ross's avatar
ross committed
246 247 248 249 250 251 252 253 254
-- | 'scanl' is similar to 'foldl', but returns a list of successive
-- reduced values from the left:
--
-- > scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
--
-- Note that
--
-- > last (scanl f z xs) == foldl f z xs.

David Feuer's avatar
David Feuer committed
255 256 257
-- This peculiar arrangement is necessary to prevent scanl being rewritten in
-- its own right-hand side.
{-# NOINLINE [1] scanl #-}
258
scanl                   :: (b -> a -> b) -> b -> [a] -> [b]
David Feuer's avatar
David Feuer committed
259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275
scanl                   = scanlGo
  where
    scanlGo           :: (b -> a -> b) -> b -> [a] -> [b]
    scanlGo f q ls    = q : (case ls of
                               []   -> []
                               x:xs -> scanlGo f (f q x) xs)

-- Note [scanl rewrite rules]
{-# RULES
"scanl"  [~1] forall f a bs . scanl f a bs =
  build (\c n -> a `c` foldr (scanlFB f c) (constScanl n) bs a)
"scanlList" [1] forall f (a::a) bs .
    foldr (scanlFB f (:)) (constScanl []) bs a = tail (scanl f a bs)
 #-}

{-# INLINE [0] scanlFB #-}
scanlFB :: (b -> a -> b) -> (b -> c -> c) -> a -> (b -> c) -> b -> c
276 277
scanlFB f c = \b g -> oneShot (\x -> let b' = f x b in b' `c` g b')
  -- See Note [Left folds via right fold]
David Feuer's avatar
David Feuer committed
278 279 280 281 282

{-# INLINE [0] constScanl #-}
constScanl :: a -> b -> a
constScanl = const

283

ross's avatar
ross committed
284 285 286 287
-- | 'scanl1' is a variant of 'scanl' that has no starting value argument:
--
-- > scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]

Don Stewart's avatar
Don Stewart committed
288 289 290
scanl1                  :: (a -> a -> a) -> [a] -> [a]
scanl1 f (x:xs)         =  scanl f x xs
scanl1 _ []             =  []
291

David Feuer's avatar
David Feuer committed
292 293 294 295 296 297 298 299
-- | A strictly accumulating version of 'scanl'
{-# NOINLINE [1] scanl' #-}
scanl'           :: (b -> a -> b) -> b -> [a] -> [b]
-- This peculiar form is needed to prevent scanl' from being rewritten
-- in its own right hand side.
scanl' = scanlGo'
  where
    scanlGo'           :: (b -> a -> b) -> b -> [a] -> [b]
300 301 302
    scanlGo' f !q ls    = q : (case ls of
                            []   -> []
                            x:xs -> scanlGo' f (f q x) xs)
David Feuer's avatar
David Feuer committed
303 304 305 306 307 308 309 310 311 312 313

-- Note [scanl rewrite rules]
{-# RULES
"scanl'"  [~1] forall f a bs . scanl' f a bs =
  build (\c n -> a `c` foldr (scanlFB' f c) (flipSeqScanl' n) bs a)
"scanlList'" [1] forall f a bs .
    foldr (scanlFB' f (:)) (flipSeqScanl' []) bs a = tail (scanl' f a bs)
 #-}

{-# INLINE [0] scanlFB' #-}
scanlFB' :: (b -> a -> b) -> (b -> c -> c) -> a -> (b -> c) -> b -> c
314 315
scanlFB' f c = \b g -> oneShot (\x -> let !b' = f x b in b' `c` g b')
  -- See Note [Left folds via right fold]
David Feuer's avatar
David Feuer committed
316 317 318

{-# INLINE [0] flipSeqScanl' #-}
flipSeqScanl' :: a -> b -> a
319
flipSeqScanl' a !_b = a
David Feuer's avatar
David Feuer committed
320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350

{-
Note [scanl rewrite rules]
~~~~~~~~~~~~~~~~~~~~~~~~~~

In most cases, when we rewrite a form to one that can fuse, we try to rewrite it
back to the original form if it does not fuse. For scanl, we do something a
little different. In particular, we rewrite

scanl f a bs

to

build (\c n -> a `c` foldr (scanlFB f c) (constScanl n) bs a)

When build is inlined, this becomes

a : foldr (scanlFB f (:)) (constScanl []) bs a

To rewrite this form back to scanl, we would need a rule that looked like

forall f a bs. a : foldr (scanlFB f (:)) (constScanl []) bs a = scanl f a bs

The problem with this rule is that it has (:) at its head. This would have the
effect of changing the way the inliner looks at (:), not only here but
everywhere.  In most cases, this makes no difference, but in some cases it
causes it to come to a different decision about whether to inline something.
Based on nofib benchmarks, this is bad for performance. Therefore, we instead
match on everything past the :, which is just the tail of scanl.
-}

351 352 353
-- foldr, foldr1, scanr, and scanr1 are the right-to-left duals of the
-- above functions.

ross's avatar
ross committed
354 355 356
-- | 'foldr1' is a variant of 'foldr' that has no starting value argument,
-- and thus must be applied to non-empty lists.

357 358 359 360 361
foldr1                  :: (a -> a -> a) -> [a] -> a
foldr1 _ [x]            =  x
foldr1 f (x:xs)         =  f x (foldr1 f xs)
foldr1 _ []             =  errorEmptyList "foldr1"

ross's avatar
ross committed
362 363 364 365
-- | 'scanr' is the right-to-left dual of 'scanl'.
-- Note that
--
-- > head (scanr f z xs) == foldr f z xs.
366
{-# NOINLINE [1] scanr #-}
367 368 369
scanr                   :: (a -> b -> b) -> b -> [a] -> [b]
scanr _ q0 []           =  [q0]
scanr f q0 (x:xs)       =  f x q : qs
Jan Stolarek's avatar
Jan Stolarek committed
370
                           where qs@(q:_) = scanr f q0 xs
371

372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388
{-# INLINE [0] strictUncurryScanr #-}
strictUncurryScanr :: (a -> b -> c) -> (a, b) -> c
strictUncurryScanr f pair = case pair of
                              (x, y) -> f x y

{-# INLINE [0] scanrFB #-}
scanrFB :: (a -> b -> b) -> (b -> c -> c) -> a -> (b, c) -> (b, c)
scanrFB f c = \x (r, est) -> (f x r, r `c` est)

{-# RULES
"scanr" [~1] forall f q0 ls . scanr f q0 ls =
  build (\c n -> strictUncurryScanr c (foldr (scanrFB f c) (q0,n) ls))
"scanrList" [1] forall f q0 ls .
               strictUncurryScanr (:) (foldr (scanrFB f (:)) (q0,[]) ls) =
                 scanr f q0 ls
 #-}

ross's avatar
ross committed
389
-- | 'scanr1' is a variant of 'scanr' that has no starting value argument.
390
scanr1                  :: (a -> a -> a) -> [a] -> [a]
Ian Lynagh's avatar
Ian Lynagh committed
391 392
scanr1 _ []             =  []
scanr1 _ [x]            =  [x]
Don Stewart's avatar
Don Stewart committed
393
scanr1 f (x:xs)         =  f x q : qs
Jan Stolarek's avatar
Jan Stolarek committed
394
                           where qs@(q:_) = scanr1 f xs
395

396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435
-- | 'maximum' returns the maximum value from a list,
-- which must be non-empty, finite, and of an ordered type.
-- It is a special case of 'Data.List.maximumBy', which allows the
-- programmer to supply their own comparison function.
maximum                 :: (Ord a) => [a] -> a
{-# INLINE [1] maximum #-}
maximum []              =  errorEmptyList "maximum"
maximum xs              =  foldl1 max xs

{-# RULES
  "maximumInt"     maximum = (strictMaximum :: [Int]     -> Int);
  "maximumInteger" maximum = (strictMaximum :: [Integer] -> Integer)
 #-}

-- We can't make the overloaded version of maximum strict without
-- changing its semantics (max might not be strict), but we can for
-- the version specialised to 'Int'.
strictMaximum           :: (Ord a) => [a] -> a
strictMaximum []        =  errorEmptyList "maximum"
strictMaximum xs        =  foldl1' max xs

-- | 'minimum' returns the minimum value from a list,
-- which must be non-empty, finite, and of an ordered type.
-- It is a special case of 'Data.List.minimumBy', which allows the
-- programmer to supply their own comparison function.
minimum                 :: (Ord a) => [a] -> a
{-# INLINE [1] minimum #-}
minimum []              =  errorEmptyList "minimum"
minimum xs              =  foldl1 min xs

{-# RULES
  "minimumInt"     minimum = (strictMinimum :: [Int]     -> Int);
  "minimumInteger" minimum = (strictMinimum :: [Integer] -> Integer)
 #-}

strictMinimum           :: (Ord a) => [a] -> a
strictMinimum []        =  errorEmptyList "minimum"
strictMinimum xs        =  foldl1' min xs


ross's avatar
ross committed
436 437 438 439 440
-- | 'iterate' @f x@ returns an infinite list of repeated applications
-- of @f@ to @x@:
--
-- > iterate f x == [x, f x, f (f x), ...]

441
{-# NOINLINE [1] iterate #-}
442
iterate :: (a -> a) -> a -> [a]
443
iterate f x =  x : iterate f (f x)
444

445
{-# NOINLINE [0] iterateFB #-}
Ian Lynagh's avatar
Ian Lynagh committed
446
iterateFB :: (a -> b -> b) -> (a -> a) -> a -> b
Joachim Breitner's avatar
Joachim Breitner committed
447 448
iterateFB c f x0 = go x0
  where go x = x `c` go (f x)
449 450

{-# RULES
Don Stewart's avatar
Don Stewart committed
451 452
"iterate"    [~1] forall f x.   iterate f x = build (\c _n -> iterateFB c f x)
"iterateFB"  [1]                iterateFB (:) = iterate
453 454 455
 #-}


ross's avatar
ross committed
456
-- | 'repeat' @x@ is an infinite list, with @x@ the value of every element.
457
repeat :: a -> [a]
458 459 460
{-# INLINE [0] repeat #-}
-- The pragma just gives the rules more chance to fire
repeat x = xs where xs = x : xs
461

Don Stewart's avatar
Don Stewart committed
462
{-# INLINE [0] repeatFB #-}     -- ditto
Ian Lynagh's avatar
Ian Lynagh committed
463
repeatFB :: (a -> b -> b) -> a -> b
464
repeatFB c x = xs where xs = x `c` xs
465

466 467

{-# RULES
468
"repeat"    [~1] forall x. repeat x = build (\c _n -> repeatFB c x)
Don Stewart's avatar
Don Stewart committed
469
"repeatFB"  [1]  repeatFB (:)       = repeat
470 471
 #-}

ross's avatar
ross committed
472 473 474 475
-- | 'replicate' @n x@ is a list of length @n@ with @x@ the value of
-- every element.
-- It is an instance of the more general 'Data.List.genericReplicate',
-- in which @n@ may be of any integral type.
476
{-# INLINE replicate #-}
477 478 479
replicate               :: Int -> a -> [a]
replicate n x           =  take n (repeat x)

ross's avatar
ross committed
480
-- | 'cycle' ties a finite list into a circular one, or equivalently,
481 482 483 484
-- the infinite repetition of the original list.  It is the identity
-- on infinite lists.

cycle                   :: [a] -> [a]
485
cycle []                = errorEmptyList "cycle"
Don Stewart's avatar
Don Stewart committed
486
cycle xs                = xs' where xs' = xs ++ xs'
487

ross's avatar
ross committed
488
-- | 'takeWhile', applied to a predicate @p@ and a list @xs@, returns the
489 490 491 492 493 494
-- longest prefix (possibly empty) of @xs@ of elements that satisfy @p@:
--
-- > takeWhile (< 3) [1,2,3,4,1,2,3,4] == [1,2]
-- > takeWhile (< 9) [1,2,3] == [1,2,3]
-- > takeWhile (< 0) [1,2,3] == []
--
495

496
{-# NOINLINE [1] takeWhile #-}
497 498
takeWhile               :: (a -> Bool) -> [a] -> [a]
takeWhile _ []          =  []
Jan Stolarek's avatar
Jan Stolarek committed
499
takeWhile p (x:xs)
500 501 502
            | p x       =  x : takeWhile p xs
            | otherwise =  []

503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521
{-# INLINE [0] takeWhileFB #-}
takeWhileFB :: (a -> Bool) -> (a -> b -> b) -> b -> a -> b -> b
takeWhileFB p c n = \x r -> if p x then x `c` r else n

-- The takeWhileFB rule is similar to the filterFB rule. It works like this:
-- takeWhileFB q (takeWhileFB p c n) n =
-- \x r -> if q x then (takeWhileFB p c n) x r else n =
-- \x r -> if q x then (\x' r' -> if p x' then x' `c` r' else n) x r else n =
-- \x r -> if q x then (if p x then x `c` r else n) else n =
-- \x r -> if q x && p x then x `c` r else n =
-- takeWhileFB (\x -> q x && p x) c n
{-# RULES
"takeWhile"     [~1] forall p xs. takeWhile p xs =
                                build (\c n -> foldr (takeWhileFB p c n) n xs)
"takeWhileList" [1]  forall p.    foldr (takeWhileFB p (:) []) [] = takeWhile p
"takeWhileFB"        forall c n p q. takeWhileFB q (takeWhileFB p c n) n =
                        takeWhileFB (\x -> q x && p x) c n
 #-}

522 523 524 525 526 527
-- | 'dropWhile' @p xs@ returns the suffix remaining after 'takeWhile' @p xs@:
--
-- > dropWhile (< 3) [1,2,3,4,5,1,2,3] == [3,4,5,1,2,3]
-- > dropWhile (< 9) [1,2,3] == []
-- > dropWhile (< 0) [1,2,3] == [1,2,3]
--
ross's avatar
ross committed
528

529 530 531 532 533 534
dropWhile               :: (a -> Bool) -> [a] -> [a]
dropWhile _ []          =  []
dropWhile p xs@(x:xs')
            | p x       =  dropWhile p xs'
            | otherwise =  xs

ross's avatar
ross committed
535
-- | 'take' @n@, applied to a list @xs@, returns the prefix of @xs@
536 537 538 539 540 541 542 543 544
-- of length @n@, or @xs@ itself if @n > 'length' xs@:
--
-- > take 5 "Hello World!" == "Hello"
-- > take 3 [1,2,3,4,5] == [1,2,3]
-- > take 3 [1,2] == [1,2]
-- > take 3 [] == []
-- > take (-1) [1,2] == []
-- > take 0 [1,2] == []
--
ross's avatar
ross committed
545 546
-- It is an instance of the more general 'Data.List.genericTake',
-- in which @n@ may be of any integral type.
547
take                   :: Int -> [a] -> [a]
ross's avatar
ross committed
548
#ifdef USE_REPORT_PRELUDE
549
take n _      | n <= 0 =  []
550
take _ []              =  []
551
take n (x:xs)          =  x : take (n-1) xs
552
#else
553 554 555 556 557 558 559

{- We always want to inline this to take advantage of a known length argument
sign. Note, however, that it's important for the RULES to grab take, rather
than trying to INLINE take immediately and then letting the RULES grab
unsafeTake. Presumably the latter approach doesn't grab it early enough; it led
to an allocation regression in nofib/fft2. -}
{-# INLINE [1] take #-}
560 561 562 563
take n xs | 0 < n     = unsafeTake n xs
          | otherwise = []

-- A version of take that takes the whole list if it's given an argument less
564
-- than 1.
565 566
{-# NOINLINE [1] unsafeTake #-}
unsafeTake :: Int -> [a] -> [a]
567 568 569
unsafeTake !_  []     = []
unsafeTake 1   (x: _) = [x]
unsafeTake m   (x:xs) = x : unsafeTake (m - 1) xs
570

571
{-# RULES
572 573 574 575
"take"     [~1] forall n xs . take n xs =
  build (\c nil -> if 0 < n
                   then foldr (takeFB c nil) (flipSeqTake nil) xs n
                   else nil)
576 577
"unsafeTakeList"  [1] forall n xs . foldr (takeFB (:) []) (flipSeqTake []) xs n
                                        = unsafeTake n xs
578 579
 #-}

580 581 582 583
{-# INLINE [0] flipSeqTake #-}
-- Just flip seq, specialized to Int, but not inlined too early.
-- It's important to force the numeric argument here, even though
-- it's not used. Otherwise, take n [] doesn't force n. This is
584 585
-- bad for strictness analysis and unboxing, and leads to increased
-- allocation in T7257.
586 587
flipSeqTake :: a -> Int -> a
flipSeqTake x !_n = x
588

589
{-# INLINE [0] takeFB #-}
590
takeFB :: (a -> b -> b) -> b -> a -> (Int -> b) -> Int -> b
591 592 593 594 595 596
-- The \m accounts for the fact that takeFB is used in a higher-order
-- way by takeFoldr, so it's better to inline.  A good example is
--     take n (repeat x)
-- for which we get excellent code... but only if we inline takeFB
-- when given four arguments
takeFB c n x xs
597 598 599 600
  = \ m -> case m of
            1 -> x `c` n
            _ -> x `c` xs (m - 1)
#endif
601 602 603 604 605 606 607 608 609 610 611 612 613 614

-- | 'drop' @n xs@ returns the suffix of @xs@
-- after the first @n@ elements, or @[]@ if @n > 'length' xs@:
--
-- > drop 6 "Hello World!" == "World!"
-- > drop 3 [1,2,3,4,5] == [4,5]
-- > drop 3 [1,2] == []
-- > drop 3 [] == []
-- > drop (-1) [1,2] == [1,2]
-- > drop 0 [1,2] == [1,2]
--
-- It is an instance of the more general 'Data.List.genericDrop',
-- in which @n@ may be of any integral type.
drop                   :: Int -> [a] -> [a]
615 616 617 618 619 620 621 622 623 624 625 626 627
#ifdef USE_REPORT_PRELUDE
drop n xs     | n <= 0 =  xs
drop _ []              =  []
drop n (_:xs)          =  drop (n-1) xs
#else /* hack away */
{-# INLINE drop #-}
drop n ls
  | n <= 0     = ls
  | otherwise  = unsafeDrop n ls
  where
    -- A version of drop that drops the whole list if given an argument
    -- less than 1
    unsafeDrop :: Int -> [a] -> [a]
628 629 630
    unsafeDrop !_ []     = []
    unsafeDrop 1  (_:xs) = xs
    unsafeDrop m  (_:xs) = unsafeDrop (m - 1) xs
631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648
#endif

-- | 'splitAt' @n xs@ returns a tuple where first element is @xs@ prefix of
-- length @n@ and second element is the remainder of the list:
--
-- > splitAt 6 "Hello World!" == ("Hello ","World!")
-- > splitAt 3 [1,2,3,4,5] == ([1,2,3],[4,5])
-- > splitAt 1 [1,2,3] == ([1],[2,3])
-- > splitAt 3 [1,2,3] == ([1,2,3],[])
-- > splitAt 4 [1,2,3] == ([1,2,3],[])
-- > splitAt 0 [1,2,3] == ([],[1,2,3])
-- > splitAt (-1) [1,2,3] == ([],[1,2,3])
--
-- It is equivalent to @('take' n xs, 'drop' n xs)@ when @n@ is not @_|_@
-- (@splitAt _|_ xs = _|_@).
-- 'splitAt' is an instance of the more general 'Data.List.genericSplitAt',
-- in which @n@ may be of any integral type.
splitAt                :: Int -> [a] -> ([a],[a])
649

650 651 652
#ifdef USE_REPORT_PRELUDE
splitAt n xs           =  (take n xs, drop n xs)
#else
653 654 655
splitAt n ls
  | n <= 0 = ([], ls)
  | otherwise          = splitAt' n ls
656
    where
657 658 659 660
        splitAt' :: Int -> [a] -> ([a], [a])
        splitAt' _  []     = ([], [])
        splitAt' 1  (x:xs) = ([x], xs)
        splitAt' m  (x:xs) = (x:xs', xs'')
Don Stewart's avatar
Don Stewart committed
661
          where
662
            (xs', xs'') = splitAt' (m - 1) xs
663 664
#endif /* USE_REPORT_PRELUDE */

665 666 667
-- | 'span', applied to a predicate @p@ and a list @xs@, returns a tuple where
-- first element is longest prefix (possibly empty) of @xs@ of elements that
-- satisfy @p@ and second element is the remainder of the list:
Jan Stolarek's avatar
Jan Stolarek committed
668
--
669 670 671
-- > span (< 3) [1,2,3,4,1,2,3,4] == ([1,2],[3,4,1,2,3,4])
-- > span (< 9) [1,2,3] == ([1,2,3],[])
-- > span (< 0) [1,2,3] == ([],[1,2,3])
Jan Stolarek's avatar
Jan Stolarek committed
672
--
673
-- 'span' @p xs@ is equivalent to @('takeWhile' p xs, 'dropWhile' p xs)@
ross's avatar
ross committed
674 675

span                    :: (a -> Bool) -> [a] -> ([a],[a])
676 677 678 679 680
span _ xs@[]            =  (xs, xs)
span p xs@(x:xs')
         | p x          =  let (ys,zs) = span p xs' in (x:ys,zs)
         | otherwise    =  ([],xs)

681 682 683
-- | 'break', applied to a predicate @p@ and a list @xs@, returns a tuple where
-- first element is longest prefix (possibly empty) of @xs@ of elements that
-- /do not satisfy/ @p@ and second element is the remainder of the list:
Jan Stolarek's avatar
Jan Stolarek committed
684
--
685 686 687 688 689
-- > break (> 3) [1,2,3,4,1,2,3,4] == ([1,2,3],[4,1,2,3,4])
-- > break (< 9) [1,2,3] == ([],[1,2,3])
-- > break (> 9) [1,2,3] == ([1,2,3],[])
--
-- 'break' @p@ is equivalent to @'span' ('not' . p)@.
ross's avatar
ross committed
690 691

break                   :: (a -> Bool) -> [a] -> ([a],[a])
692 693 694 695
#ifdef USE_REPORT_PRELUDE
break p                 =  span (not . p)
#else
-- HBC version (stolen)
Don Stewart's avatar
Don Stewart committed
696
break _ xs@[]           =  (xs, xs)
697
break p xs@(x:xs')
Don Stewart's avatar
Don Stewart committed
698 699
           | p x        =  ([],xs)
           | otherwise  =  let (ys,zs) = break p xs' in (x:ys,zs)
700 701
#endif

ross's avatar
ross committed
702 703
-- | 'reverse' @xs@ returns the elements of @xs@ in reverse order.
-- @xs@ must be finite.
704 705 706 707 708 709 710 711 712 713
reverse                 :: [a] -> [a]
#ifdef USE_REPORT_PRELUDE
reverse                 =  foldl (flip (:)) []
#else
reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)
#endif

ross's avatar
ross committed
714 715 716 717
-- | 'and' returns the conjunction of a Boolean list.  For the result to be
-- 'True', the list must be finite; 'False', however, results from a 'False'
-- value at a finite index of a finite or infinite list.
and                     :: [Bool] -> Bool
718 719 720 721 722 723 724 725 726 727 728 729
#ifdef USE_REPORT_PRELUDE
and                     =  foldr (&&) True
#else
and []          =  True
and (x:xs)      =  x && and xs
{-# NOINLINE [1] and #-}

{-# RULES
"and/build"     forall (g::forall b.(Bool->b->b)->b->b) .
                and (build g) = g (&&) True
 #-}
#endif
ross's avatar
ross committed
730 731 732 733 734

-- | 'or' returns the disjunction of a Boolean list.  For the result to be
-- 'False', the list must be finite; 'True', however, results from a 'True'
-- value at a finite index of a finite or infinite list.
or                      :: [Bool] -> Bool
735 736 737
#ifdef USE_REPORT_PRELUDE
or                      =  foldr (||) False
#else
Don Stewart's avatar
Don Stewart committed
738 739
or []           =  False
or (x:xs)       =  x || or xs
740 741
{-# NOINLINE [1] or #-}

742
{-# RULES
Jan Stolarek's avatar
Jan Stolarek committed
743
"or/build"      forall (g::forall b.(Bool->b->b)->b->b) .
Don Stewart's avatar
Don Stewart committed
744
                or (build g) = g (||) False
745 746 747
 #-}
#endif

ross's avatar
ross committed
748
-- | Applied to a predicate and a list, 'any' determines if any element
749 750 751
-- of the list satisfies the predicate.  For the result to be
-- 'False', the list must be finite; 'True', however, results from a 'True'
-- value for the predicate applied to an element at a finite index of a finite or infinite list.
ross's avatar
ross committed
752 753
any                     :: (a -> Bool) -> [a] -> Bool

754 755 756 757 758 759 760 761 762 763 764 765 766 767
#ifdef USE_REPORT_PRELUDE
any p                   =  or . map p
#else
any _ []        = False
any p (x:xs)    = p x || any p xs

{-# NOINLINE [1] any #-}

{-# RULES
"any/build"     forall p (g::forall b.(a->b->b)->b->b) .
                any p (build g) = g ((||) . p) False
 #-}
#endif

ross's avatar
ross committed
768
-- | Applied to a predicate and a list, 'all' determines if all elements
769 770 771
-- of the list satisfy the predicate. For the result to be
-- 'True', the list must be finite; 'False', however, results from a 'False'
-- value for the predicate applied to an element at a finite index of a finite or infinite list.
ross's avatar
ross committed
772
all                     :: (a -> Bool) -> [a] -> Bool
773 774 775
#ifdef USE_REPORT_PRELUDE
all p                   =  and . map p
#else
Don Stewart's avatar
Don Stewart committed
776 777
all _ []        =  True
all p (x:xs)    =  p x && all p xs
778 779 780

{-# NOINLINE [1] all #-}

781
{-# RULES
Jan Stolarek's avatar
Jan Stolarek committed
782
"all/build"     forall p (g::forall b.(a->b->b)->b->b) .
Don Stewart's avatar
Don Stewart committed
783
                all p (build g) = g ((&&) . p) True
784 785 786
 #-}
#endif

ross's avatar
ross committed
787
-- | 'elem' is the list membership predicate, usually written in infix form,
788
-- e.g., @x \`elem\` xs@.  For the result to be
789 790
-- 'False', the list must be finite; 'True', however, results from an element
-- equal to @x@ found at a finite index of a finite or infinite list.
ross's avatar
ross committed
791
elem                    :: (Eq a) => a -> [a] -> Bool
792 793 794
#ifdef USE_REPORT_PRELUDE
elem x                  =  any (== x)
#else
Don Stewart's avatar
Don Stewart committed
795 796
elem _ []       = False
elem x (y:ys)   = x==y || elem x ys
797 798 799 800 801 802
{-# NOINLINE [1] elem #-}
{-# RULES
"elem/build"    forall x (g :: forall b . Eq a => (a -> b -> b) -> b -> b)
   . elem x (build g) = g (\ y r -> (x == y) || r) False
 #-}
#endif
803

804 805 806 807 808
-- | 'notElem' is the negation of 'elem'.
notElem                 :: (Eq a) => a -> [a] -> Bool
#ifdef USE_REPORT_PRELUDE
notElem x               =  all (/= x)
#else
Don Stewart's avatar
Don Stewart committed
809
notElem _ []    =  True
810
notElem x (y:ys)=  x /= y && notElem x ys
811 812 813 814 815
{-# NOINLINE [1] notElem #-}
{-# RULES
"notElem/build" forall x (g :: forall b . Eq a => (a -> b -> b) -> b -> b)
   . notElem x (build g) = g (\ y r -> (x /= y) && r) True
 #-}
816 817
#endif

ross's avatar
ross committed
818
-- | 'lookup' @key assocs@ looks up a key in an association list.
819 820 821 822 823 824
lookup                  :: (Eq a) => a -> [(a,b)] -> Maybe b
lookup _key []          =  Nothing
lookup  key ((x,y):xys)
    | key == x          =  Just y
    | otherwise         =  lookup key xys

ross's avatar
ross committed
825
-- | Map a function over a list and concatenate the results.
826 827 828
concatMap               :: (a -> [b]) -> [a] -> [b]
concatMap f             =  foldr ((++) . f) []

829 830 831 832 833 834 835 836
{-# NOINLINE [1] concatMap #-}

{-# RULES
"concatMap" forall f xs . concatMap f xs =
    build (\c n -> foldr (\x b -> foldr c b (f x)) n xs)
 #-}


ross's avatar
ross committed
837
-- | Concatenate a list of lists.
838 839 840
concat :: [[a]] -> [a]
concat = foldr (++) []

841 842
{-# NOINLINE [1] concat #-}

843
{-# RULES
844 845
  "concat" forall xs. concat xs =
     build (\c n -> foldr (\x y -> foldr c y x) n xs)
846
-- We don't bother to turn non-fusible applications of concat back into concat
847
 #-}
848

ross's avatar
ross committed
849 850 851
-- | List index (subscript) operator, starting from 0.
-- It is an instance of the more general 'Data.List.genericIndex',
-- which takes an index of any integral type.
852 853
(!!)                    :: [a] -> Int -> a
#ifdef USE_REPORT_PRELUDE
854 855 856 857
xs     !! n | n < 0 =  error "Prelude.!!: negative index"
[]     !! _         =  error "Prelude.!!: index too large"
(x:_)  !! 0         =  x
(_:xs) !! n         =  xs !! (n-1)
858
#else
859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875

-- We don't really want the errors to inline with (!!).
-- We may want to fuss around a bit with NOINLINE, and
-- if so we should be careful not to trip up known-bottom
-- optimizations.
tooLarge :: Int -> a
tooLarge _ = error (prel_list_str ++ "!!: index too large")

negIndex :: a
negIndex = error $ prel_list_str ++ "!!: negative index"

{-# INLINABLE (!!) #-}
xs !! n
  | n < 0     = negIndex
  | otherwise = foldr (\x r k -> case k of
                                   0 -> x
                                   _ -> r (k-1)) tooLarge xs n
876 877
#endif

878 879 880
--------------------------------------------------------------
-- The zip family
--------------------------------------------------------------
881

Ian Lynagh's avatar
Ian Lynagh committed
882
foldr2 :: (a -> b -> c -> c) -> c -> [a] -> [b] -> c
Joachim Breitner's avatar
Joachim Breitner committed
883 884
foldr2 k z = go
  where
885
        go []    _ys     = z
886 887
        go _xs   []      = z
        go (x:xs) (y:ys) = k x y (go xs ys)
Joachim Breitner's avatar
Joachim Breitner committed
888
{-# INLINE [0] foldr2 #-}
889

Ian Lynagh's avatar
Ian Lynagh committed
890
foldr2_left :: (a -> b -> c -> d) -> d -> a -> ([b] -> c) -> [b] -> d
891 892 893 894 895
foldr2_left _k  z _x _r []     = z
foldr2_left  k _z  x  r (y:ys) = k x y (r ys)

-- foldr2 k z xs ys = foldr (foldr2_left k z)  (\_ -> z) xs ys
{-# RULES
Jan Stolarek's avatar
Jan Stolarek committed
896
"foldr2/left"   forall k z ys (g::forall b.(a->b->b)->b->b) .
Don Stewart's avatar
Don Stewart committed
897
                  foldr2 k z (build g) ys = g (foldr2_left  k z) (\_ -> z) ys
898
 #-}
899 900 901 902 903 904 905 906 907 908 909 910 911 912 913
-- There used to be a foldr2/right rule, allowing foldr2 to fuse with a build
-- form on the right. However, this causes trouble if the right list ends in
-- a bottom that is only avoided by the left list ending at that spot. That is,
-- foldr2 f z [a,b,c] (d:e:f:_|_), where the right list is produced by a build
-- form, would cause the foldr2/right rule to introduce bottom. Example:
--
-- zip [1,2,3,4] (unfoldr (\s -> if s > 4 then undefined else Just (s,s+1)) 1)
--
-- should produce
--
-- [(1,1),(2,2),(3,3),(4,4)]
--
-- but with the foldr2/right rule it would instead produce
--
-- (1,1):(2,2):(3,3):(4,4):_|_
914

915 916
-- Zips for larger tuples are in the List module.

917
----------------------------------------------
ross's avatar
ross committed
918 919 920
-- | 'zip' takes two lists and returns a list of corresponding pairs.
-- If one input list is short, excess elements of the longer list are
-- discarded.
David Feuer's avatar
David Feuer committed
921
--
922 923 924
-- 'zip' is right-lazy:
--
-- > zip [] _|_ = []
925
{-# NOINLINE [1] zip #-}
926
zip :: [a] -> [b] -> [(a,b)]
927
zip []     _bs    = []
David Feuer's avatar
David Feuer committed
928
zip _as    []     = []
929
zip (a:as) (b:bs) = (a,b) : zip as bs
930

931
{-# INLINE [0] zipFB #-}
Ian Lynagh's avatar
Ian Lynagh committed
932
zipFB :: ((a, b) -> c -> d) -> a -> b -> c -> d
933
zipFB c = \x y r -> (x,y) `c` r
934 935

{-# RULES
Don Stewart's avatar
Don Stewart committed
936 937
"zip"      [~1] forall xs ys. zip xs ys = build (\c n -> foldr2 (zipFB c) n xs ys)
"zipList"  [1]  foldr2 (zipFB (:)) []   = zip
938 939 940
 #-}

----------------------------------------------
ross's avatar
ross committed
941 942
-- | 'zip3' takes three lists and returns a list of triples, analogous to
-- 'zip'.
943 944 945 946 947 948 949 950 951 952 953
zip3 :: [a] -> [b] -> [c] -> [(a,b,c)]
-- Specification
-- zip3 =  zipWith3 (,,)
zip3 (a:as) (b:bs) (c:cs) = (a,b,c) : zip3 as bs cs
zip3 _      _      _      = []


-- The zipWith family generalises the zip family by zipping with the
-- function given as the first argument, instead of a tupling function.

----------------------------------------------
ross's avatar
ross committed
954 955 956 957
-- | 'zipWith' generalises 'zip' by zipping with the function given
-- as the first argument, instead of a tupling function.
-- For example, @'zipWith' (+)@ is applied to two lists to produce the
-- list of corresponding sums.
David Feuer's avatar
David Feuer committed
958
--
959 960 961
-- 'zipWith' is right-lazy:
--
-- > zipWith f [] _|_ = []
962
{-# NOINLINE [1] zipWith #-}
963
zipWith :: (a->b->c) -> [a]->[b]->[c]
964
zipWith _f []     _bs    = []
David Feuer's avatar
David Feuer committed
965 966
zipWith _f _as    []     = []
zipWith f  (a:as) (b:bs) = f a b : zipWith f as bs
967

968 969
-- zipWithFB must have arity 2 since it gets two arguments in the "zipWith"
-- rule; it might not get inlined otherwise
970
{-# INLINE [0] zipWithFB #-}
Ian Lynagh's avatar
Ian Lynagh committed
971
zipWithFB :: (a -> b -> c) -> (d -> e -> a) -> d -> e -> b -> c
972
zipWithFB c f = \x y r -> (x `f` y) `c` r
973 974

{-# RULES
Don Stewart's avatar
Don Stewart committed
975 976
"zipWith"       [~1] forall f xs ys.    zipWith f xs ys = build (\c n -> foldr2 (zipWithFB c f) n xs ys)
"zipWithList"   [1]  forall f.  foldr2 (zipWithFB (:) f) [] = zipWith f
977 978
  #-}

ross's avatar
ross committed
979 980 981
-- | The 'zipWith3' function takes a function which combines three
-- elements, as well as three lists and returns a list of their point-wise
-- combination, analogous to 'zipWith'.
982 983 984 985 986
zipWith3                :: (a->b->c->d) -> [a]->[b]->[c]->[d]
zipWith3 z (a:as) (b:bs) (c:cs)
                        =  z a b c : zipWith3 z as bs cs
zipWith3 _ _ _ _        =  []

ross's avatar
ross committed
987 988
-- | 'unzip' transforms a list of pairs into a list of first components
-- and a list of second components.
989 990 991 992
unzip    :: [(a,b)] -> ([a],[b])
{-# INLINE unzip #-}
unzip    =  foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])

ross's avatar
ross committed
993 994
-- | The 'unzip3' function takes a list of triples and returns three
-- lists, analogous to 'unzip'.
995 996 997 998 999
unzip3   :: [(a,b,c)] -> ([a],[b],[c])
{-# INLINE unzip3 #-}
unzip3   =  foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
                  ([],[],[])

1000 1001 1002
--------------------------------------------------------------
-- Error code
--------------------------------------------------------------
1003

1004 1005
-- Common up near identical calls to `error' to reduce the number
-- constant strings created when compiled:
1006 1007 1008 1009 1010 1011 1012

errorEmptyList :: String -> a
errorEmptyList fun =
  error (prel_list_str ++ fun ++ ": empty list")

prel_list_str :: String
prel_list_str = "Prelude."