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

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

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

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

 ) where

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

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

43 44 45
--------------------------------------------------------------
-- List-manipulation functions
--------------------------------------------------------------
46

47
-- | \(\mathcal{O}(1)\). Extract the first element of a list, which must be non-empty.
48 49 50
head                    :: [a] -> a
head (x:_)              =  x
head []                 =  badHead
51
{-# NOINLINE [1] head #-}
52

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

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

65 66
-- | \(\mathcal{O}(1)\). 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)@,
David Feuer's avatar
David Feuer committed
67
-- where @x@ is the head of the list and @xs@ its tail.
68
--
69
-- @since 4.8.0.0
David Feuer's avatar
David Feuer committed
70 71 72 73
uncons                  :: [a] -> Maybe (a, [a])
uncons []               = Nothing
uncons (x:xs)           = Just (x, xs)

74 75
-- | \(\mathcal{O}(1)\). 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"

80 81
-- | \(\mathcal{O}(n)\). Extract the last element of a list, which must be
-- finite and non-empty.
82
last                    :: [a] -> a
Ben Gamari's avatar
Ben Gamari committed
83
#if defined(USE_REPORT_PRELUDE)
84 85 86 87
last [x]                =  x
last (_:xs)             =  last xs
last []                 =  errorEmptyList "last"
#else
88 89 90 91 92 93 94 95 96
-- 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"
97 98
#endif

99
-- | \(\mathcal{O}(n)\). Return all the elements of a list except the last one.
100
-- The list must be non-empty.
101
init                    :: [a] -> [a]
Ben Gamari's avatar
Ben Gamari committed
102
#if defined(USE_REPORT_PRELUDE)
103 104 105 106 107 108 109 110
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
111
        init' y (z:zs) = y : init' z zs
112 113
#endif

114
-- | \(\mathcal{O}(1)\). Test whether a list is empty.
115 116 117 118
null                    :: [a] -> Bool
null []                 =  True
null (_:_)              =  False

119 120 121
-- | \(\mathcal{O}(n)\). 'length' returns the length of a finite list as an
-- 'Int'. It is an instance of the more general 'Data.List.genericLength', the
-- result type of which may be any kind of number.
122
{-# NOINLINE [1] length #-}
123
length                  :: [a] -> Int
124
length xs               = lenAcc xs 0
125

126 127 128
lenAcc          :: [a] -> Int -> Int
lenAcc []     n = n
lenAcc (_:ys) n = lenAcc ys (n+1)
129 130

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

135 136 137 138
-- 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
139
lengthFB _ r = \ !a -> r (a + 1)
140 141 142 143 144

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

145 146
-- | \(\mathcal{O}(n)\). 'filter', applied to a predicate and a list, returns
-- the list of those elements that satisfy the predicate; i.e.,
ross's avatar
ross committed
147 148
--
-- > filter p xs = [ x | x <- xs, p x]
149 150 151
--
-- >>> filter odd [1, 2, 3]
-- [1,3]
ross's avatar
ross committed
152

153
{-# NOINLINE [1] filter #-}
154
filter :: (a -> Bool) -> [a] -> [a]
155 156 157
filter _pred []    = []
filter pred (x:xs)
  | pred x         = x : filter pred xs
Don Stewart's avatar
Don Stewart committed
158
  | otherwise      = filter pred xs
159

160
{-# INLINE [0] filterFB #-} -- See Note [Inline FB functions]
Ian Lynagh's avatar
Ian Lynagh committed
161
filterFB :: (a -> b -> b) -> (a -> Bool) -> a -> b -> b
162
filterFB c p x r | p x       = x `c` r
Don Stewart's avatar
Don Stewart committed
163
                 | otherwise = r
164 165

{-# RULES
166
"filter"     [~1] forall p xs.  filter p xs = build (\c n -> foldr (filterFB c p) n xs)
Don Stewart's avatar
Don Stewart committed
167 168
"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)
169 170 171 172 173 174 175 176 177 178 179 180
 #-}

-- 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
181 182 183 184 185 186 187
-- | '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.
188

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
  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
Simon Peyton Jones's avatar
Simon Peyton Jones committed
210
arguments to foldr, where we know how the arguments are called.
211

212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228
Note [Inline FB functions]
~~~~~~~~~~~~~~~~~~~~~~~~~~
After fusion rules successfully fire, we are usually left with one or more calls
to list-producing functions abstracted over cons and nil. Here we call them
FB functions because their names usually end with 'FB'. It's a good idea to
inline FB functions because:

* They are higher-order functions and therefore benefits from inlining.

* When the final consumer is a left fold, inlining the FB functions is the only
  way to make arity expansion to happen. See Note [Left fold via right fold].

For this reason we mark all FB functions INLINE [0]. The [0] phase-specifier
ensures that calls to FB functions can be written back to the original form
when no fusion happens.

Without these inline pragmas, the loop in perf/should_run/T13001 won't be
229
allocation-free. Also see #13001.
230 231
-}

232 233 234 235 236 237
-- ----------------------------------------------------------------------------

-- | A strict version of 'foldl'.
foldl'           :: forall a b . (b -> a -> b) -> b -> [a] -> b
{-# INLINE foldl' #-}
foldl' k z0 xs =
238 239
  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]
240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263

-- | '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
264

265 266
-- | \(\mathcal{O}(n)\). 'scanl' is similar to 'foldl', but returns a list of
-- successive reduced values from the left:
ross's avatar
ross committed
267 268 269 270 271 272 273
--
-- > 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
274 275 276
-- This peculiar arrangement is necessary to prevent scanl being rewritten in
-- its own right-hand side.
{-# NOINLINE [1] scanl #-}
277
scanl                   :: (b -> a -> b) -> b -> [a] -> [b]
David Feuer's avatar
David Feuer committed
278 279 280 281 282 283 284 285 286 287 288 289 290 291 292
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)
 #-}

293
{-# INLINE [0] scanlFB #-} -- See Note [Inline FB functions]
David Feuer's avatar
David Feuer committed
294
scanlFB :: (b -> a -> b) -> (b -> c -> c) -> a -> (b -> c) -> b -> c
295 296
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
297 298 299 300 301

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

302

303 304
-- | \(\mathcal{O}(n)\). 'scanl1' is a variant of 'scanl' that has no starting
-- value argument:
ross's avatar
ross committed
305 306 307
--
-- > scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]

Don Stewart's avatar
Don Stewart committed
308 309 310
scanl1                  :: (a -> a -> a) -> [a] -> [a]
scanl1 f (x:xs)         =  scanl f x xs
scanl1 _ []             =  []
311

312
-- | \(\mathcal{O}(n)\). A strictly accumulating version of 'scanl'
David Feuer's avatar
David Feuer committed
313 314 315 316 317 318 319
{-# 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]
320 321 322
    scanlGo' f !q ls    = q : (case ls of
                            []   -> []
                            x:xs -> scanlGo' f (f q x) xs)
David Feuer's avatar
David Feuer committed
323 324 325 326 327 328 329 330 331

-- 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)
 #-}

332
{-# INLINE [0] scanlFB' #-} -- See Note [Inline FB functions]
David Feuer's avatar
David Feuer committed
333
scanlFB' :: (b -> a -> b) -> (b -> c -> c) -> a -> (b -> c) -> b -> c
334 335
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
336 337 338

{-# INLINE [0] flipSeqScanl' #-}
flipSeqScanl' :: a -> b -> a
339
flipSeqScanl' a !_b = a
David Feuer's avatar
David Feuer committed
340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370

{-
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.
-}

371 372 373
-- foldr, foldr1, scanr, and scanr1 are the right-to-left duals of the
-- above functions.

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

377
foldr1                  :: (a -> a -> a) -> [a] -> a
378 379 380 381 382
foldr1 f = go
  where go [x]            =  x
        go (x:xs)         =  f x (go xs)
        go []             =  errorEmptyList "foldr1"
{-# INLINE [0] foldr1 #-}
383

384
-- | \(\mathcal{O}(n)\). 'scanr' is the right-to-left dual of 'scanl'.
ross's avatar
ross committed
385 386 387
-- Note that
--
-- > head (scanr f z xs) == foldr f z xs.
388 389 390
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
391
                           where qs@(q:_) = scanr f q0 xs
392

393 394
-- | \(\mathcal{O}(n)\). 'scanr1' is a variant of 'scanr' that has no starting
-- value argument.
395
scanr1                  :: (a -> a -> a) -> [a] -> [a]
Ian Lynagh's avatar
Ian Lynagh committed
396 397
scanr1 _ []             =  []
scanr1 _ [x]            =  [x]
Don Stewart's avatar
Don Stewart committed
398
scanr1 f (x:xs)         =  f x q : qs
Jan Stolarek's avatar
Jan Stolarek committed
399
                           where qs@(q:_) = scanr1 f xs
400

401 402 403 404 405
-- | '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
406
{-# INLINABLE maximum #-}
407 408 409
maximum []              =  errorEmptyList "maximum"
maximum xs              =  foldl1 max xs

410 411 412 413 414
-- We want this to be specialized so that with a strict max function, GHC
-- produces good code. Note that to see if this is happending, one has to
-- look at -ddump-prep, not -ddump-core!
{-# SPECIALIZE  maximum :: [Int] -> Int #-}
{-# SPECIALIZE  maximum :: [Integer] -> Integer #-}
415 416 417 418 419 420

-- | '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
421
{-# INLINABLE minimum #-}
422 423 424
minimum []              =  errorEmptyList "minimum"
minimum xs              =  foldl1 min xs

425 426
{-# SPECIALIZE  minimum :: [Int] -> Int #-}
{-# SPECIALIZE  minimum :: [Integer] -> Integer #-}
427 428


ross's avatar
ross committed
429 430 431 432
-- | 'iterate' @f x@ returns an infinite list of repeated applications
-- of @f@ to @x@:
--
-- > iterate f x == [x, f x, f (f x), ...]
Ben Gamari's avatar
Ben Gamari committed
433 434
--
-- Note that 'iterate' is lazy, potentially leading to thunk build-up if
David Sanders's avatar
David Sanders committed
435
-- the consumer doesn't force each iterate. See 'iterate'' for a strict
Ben Gamari's avatar
Ben Gamari committed
436
-- variant of this function.
437
{-# NOINLINE [1] iterate #-}
438
iterate :: (a -> a) -> a -> [a]
439
iterate f x =  x : iterate f (f x)
440

441
{-# INLINE [0] iterateFB #-} -- See Note [Inline FB functions]
Ian Lynagh's avatar
Ian Lynagh committed
442
iterateFB :: (a -> b -> b) -> (a -> a) -> a -> b
Joachim Breitner's avatar
Joachim Breitner committed
443 444
iterateFB c f x0 = go x0
  where go x = x `c` go (f x)
445 446

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


David Sanders's avatar
David Sanders committed
452
-- | 'iterate'' is the strict version of 'iterate'.
Ben Gamari's avatar
Ben Gamari committed
453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474
--
-- It ensures that the result of each application of force to weak head normal
-- form before proceeding.
{-# NOINLINE [1] iterate' #-}
iterate' :: (a -> a) -> a -> [a]
iterate' f x =
    let x' = f x
    in x' `seq` (x : iterate' f x')

{-# INLINE [0] iterate'FB #-} -- See Note [Inline FB functions]
iterate'FB :: (a -> b -> b) -> (a -> a) -> a -> b
iterate'FB c f x0 = go x0
  where go x =
            let x' = f x
            in x' `seq` (x `c` go x')

{-# RULES
"iterate'"    [~1] forall f x.   iterate' f x = build (\c _n -> iterate'FB c f x)
"iterate'FB"  [1]                iterate'FB (:) = iterate'
 #-}


ross's avatar
ross committed
475
-- | 'repeat' @x@ is an infinite list, with @x@ the value of every element.
476
repeat :: a -> [a]
477 478 479
{-# INLINE [0] repeat #-}
-- The pragma just gives the rules more chance to fire
repeat x = xs where xs = x : xs
480

481
{-# INLINE [0] repeatFB #-}     -- ditto -- See Note [Inline FB functions]
Ian Lynagh's avatar
Ian Lynagh committed
482
repeatFB :: (a -> b -> b) -> a -> b
483
repeatFB c x = xs where xs = x `c` xs
484

485 486

{-# RULES
487
"repeat"    [~1] forall x. repeat x = build (\c _n -> repeatFB c x)
Don Stewart's avatar
Don Stewart committed
488
"repeatFB"  [1]  repeatFB (:)       = repeat
489 490
 #-}

ross's avatar
ross committed
491 492 493 494
-- | '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.
495
{-# INLINE replicate #-}
496 497 498
replicate               :: Int -> a -> [a]
replicate n x           =  take n (repeat x)

ross's avatar
ross committed
499
-- | 'cycle' ties a finite list into a circular one, or equivalently,
500 501 502 503
-- the infinite repetition of the original list.  It is the identity
-- on infinite lists.

cycle                   :: [a] -> [a]
504
cycle []                = errorEmptyList "cycle"
Don Stewart's avatar
Don Stewart committed
505
cycle xs                = xs' where xs' = xs ++ xs'
506

ross's avatar
ross committed
507
-- | 'takeWhile', applied to a predicate @p@ and a list @xs@, returns the
508 509 510 511 512 513
-- 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] == []
--
514

515
{-# NOINLINE [1] takeWhile #-}
516 517
takeWhile               :: (a -> Bool) -> [a] -> [a]
takeWhile _ []          =  []
Jan Stolarek's avatar
Jan Stolarek committed
518
takeWhile p (x:xs)
519 520 521
            | p x       =  x : takeWhile p xs
            | otherwise =  []

522
{-# INLINE [0] takeWhileFB #-} -- See Note [Inline FB functions]
523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540
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
 #-}

541 542 543 544 545 546
-- | '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
547

548 549 550 551 552 553
dropWhile               :: (a -> Bool) -> [a] -> [a]
dropWhile _ []          =  []
dropWhile p xs@(x:xs')
            | p x       =  dropWhile p xs'
            | otherwise =  xs

ross's avatar
ross committed
554
-- | 'take' @n@, applied to a list @xs@, returns the prefix of @xs@
555 556 557 558 559 560 561 562 563
-- 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
564 565
-- It is an instance of the more general 'Data.List.genericTake',
-- in which @n@ may be of any integral type.
566
take                   :: Int -> [a] -> [a]
Ben Gamari's avatar
Ben Gamari committed
567
#if defined(USE_REPORT_PRELUDE)
568
take n _      | n <= 0 =  []
569
take _ []              =  []
570
take n (x:xs)          =  x : take (n-1) xs
571
#else
572 573 574 575 576 577 578

{- 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 #-}
579 580 581 582
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
583
-- than 1.
584 585
{-# NOINLINE [1] unsafeTake #-}
unsafeTake :: Int -> [a] -> [a]
586 587 588
unsafeTake !_  []     = []
unsafeTake 1   (x: _) = [x]
unsafeTake m   (x:xs) = x : unsafeTake (m - 1) xs
589

590
{-# RULES
591 592 593 594
"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)
595 596
"unsafeTakeList"  [1] forall n xs . foldr (takeFB (:) []) (flipSeqTake []) xs n
                                        = unsafeTake n xs
597 598
 #-}

599 600 601 602
{-# 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
603 604
-- bad for strictness analysis and unboxing, and leads to increased
-- allocation in T7257.
605 606
flipSeqTake :: a -> Int -> a
flipSeqTake x !_n = x
607

608
{-# INLINE [0] takeFB #-} -- See Note [Inline FB functions]
609
takeFB :: (a -> b -> b) -> b -> a -> (Int -> b) -> Int -> b
610 611 612 613 614 615
-- 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
616 617 618 619
  = \ m -> case m of
            1 -> x `c` n
            _ -> x `c` xs (m - 1)
#endif
620 621 622 623 624 625 626 627 628 629 630 631 632 633

-- | '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]
Ben Gamari's avatar
Ben Gamari committed
634
#if defined(USE_REPORT_PRELUDE)
635 636 637 638 639 640 641 642 643 644 645 646
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]
647 648 649
    unsafeDrop !_ []     = []
    unsafeDrop 1  (_:xs) = xs
    unsafeDrop m  (_:xs) = unsafeDrop (m - 1) xs
650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667
#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])
668

Ben Gamari's avatar
Ben Gamari committed
669
#if defined(USE_REPORT_PRELUDE)
670 671
splitAt n xs           =  (take n xs, drop n xs)
#else
672 673 674
splitAt n ls
  | n <= 0 = ([], ls)
  | otherwise          = splitAt' n ls
675
    where
676 677 678 679
        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
680
          where
681
            (xs', xs'') = splitAt' (m - 1) xs
682 683
#endif /* USE_REPORT_PRELUDE */

684 685 686
-- | '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
687
--
688 689 690
-- > 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
691
--
692
-- 'span' @p xs@ is equivalent to @('takeWhile' p xs, 'dropWhile' p xs)@
ross's avatar
ross committed
693 694

span                    :: (a -> Bool) -> [a] -> ([a],[a])
695 696 697 698 699
span _ xs@[]            =  (xs, xs)
span p xs@(x:xs')
         | p x          =  let (ys,zs) = span p xs' in (x:ys,zs)
         | otherwise    =  ([],xs)

700 701 702
-- | '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
703
--
704 705 706 707 708
-- > 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
709 710

break                   :: (a -> Bool) -> [a] -> ([a],[a])
Ben Gamari's avatar
Ben Gamari committed
711
#if defined(USE_REPORT_PRELUDE)
712 713 714
break p                 =  span (not . p)
#else
-- HBC version (stolen)
Don Stewart's avatar
Don Stewart committed
715
break _ xs@[]           =  (xs, xs)
716
break p xs@(x:xs')
Don Stewart's avatar
Don Stewart committed
717 718
           | p x        =  ([],xs)
           | otherwise  =  let (ys,zs) = break p xs' in (x:ys,zs)
719 720
#endif

ross's avatar
ross committed
721 722
-- | 'reverse' @xs@ returns the elements of @xs@ in reverse order.
-- @xs@ must be finite.
723
reverse                 :: [a] -> [a]
Ben Gamari's avatar
Ben Gamari committed
724
#if defined(USE_REPORT_PRELUDE)
725 726 727 728 729 730 731 732
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
733 734 735 736
-- | '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
Ben Gamari's avatar
Ben Gamari committed
737
#if defined(USE_REPORT_PRELUDE)
738 739 740 741 742 743 744 745 746 747 748
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
749 750 751 752 753

-- | '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
Ben Gamari's avatar
Ben Gamari committed
754
#if defined(USE_REPORT_PRELUDE)
755 756
or                      =  foldr (||) False
#else
Don Stewart's avatar
Don Stewart committed
757 758
or []           =  False
or (x:xs)       =  x || or xs
759 760
{-# NOINLINE [1] or #-}

761
{-# RULES
Jan Stolarek's avatar
Jan Stolarek committed
762
"or/build"      forall (g::forall b.(Bool->b->b)->b->b) .
Don Stewart's avatar
Don Stewart committed
763
                or (build g) = g (||) False
764 765 766
 #-}
#endif

ross's avatar
ross committed
767
-- | Applied to a predicate and a list, 'any' determines if any element
768 769 770
-- 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
771 772
any                     :: (a -> Bool) -> [a] -> Bool

Ben Gamari's avatar
Ben Gamari committed
773
#if defined(USE_REPORT_PRELUDE)
774 775 776 777 778 779 780 781 782 783 784 785 786
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
787
-- | Applied to a predicate and a list, 'all' determines if all elements
788 789 790
-- 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
791
all                     :: (a -> Bool) -> [a] -> Bool
Ben Gamari's avatar
Ben Gamari committed
792
#if defined(USE_REPORT_PRELUDE)
793 794
all p                   =  and . map p
#else
Don Stewart's avatar
Don Stewart committed
795 796
all _ []        =  True
all p (x:xs)    =  p x && all p xs
797 798 799

{-# NOINLINE [1] all #-}

800
{-# RULES
Jan Stolarek's avatar
Jan Stolarek committed
801
"all/build"     forall p (g::forall b.(a->b->b)->b->b) .
Don Stewart's avatar
Don Stewart committed
802
                all p (build g) = g ((&&) . p) True
803 804 805
 #-}
#endif

ross's avatar
ross committed
806
-- | 'elem' is the list membership predicate, usually written in infix form,
807
-- e.g., @x \`elem\` xs@.  For the result to be
808 809
-- '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
810
elem                    :: (Eq a) => a -> [a] -> Bool
Ben Gamari's avatar
Ben Gamari committed
811
#if defined(USE_REPORT_PRELUDE)
812 813
elem x                  =  any (== x)
#else
Don Stewart's avatar
Don Stewart committed
814 815
elem _ []       = False
elem x (y:ys)   = x==y || elem x ys
816 817 818 819 820 821
{-# 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
822

823 824
-- | 'notElem' is the negation of 'elem'.
notElem                 :: (Eq a) => a -> [a] -> Bool
Ben Gamari's avatar
Ben Gamari committed
825
#if defined(USE_REPORT_PRELUDE)
826 827
notElem x               =  all (/= x)
#else
Don Stewart's avatar
Don Stewart committed
828
notElem _ []    =  True
829
notElem x (y:ys)=  x /= y && notElem x ys
830 831 832 833 834
{-# 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
 #-}
835 836
#endif

837 838
-- | \(\mathcal{O}(n)\). 'lookup' @key assocs@ looks up a key in an association
-- list.
839 840 841
--
-- >>> lookup 2 [(1, "first"), (2, "second"), (3, "third")]
-- Just "second"
842 843 844
lookup                  :: (Eq a) => a -> [(a,b)] -> Maybe b
lookup _key []          =  Nothing
lookup  key ((x,y):xys)
845
    | key == x           =  Just y
846 847
    | otherwise         =  lookup key xys

ross's avatar
ross committed
848
-- | Map a function over a list and concatenate the results.
849 850 851
concatMap               :: (a -> [b]) -> [a] -> [b]
concatMap f             =  foldr ((++) . f) []

852 853 854 855 856 857 858 859
{-# 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
860
-- | Concatenate a list of lists.
861 862 863
concat :: [[a]] -> [a]
concat = foldr (++) []

864 865
{-# NOINLINE [1] concat #-}

866
{-# RULES
867 868
  "concat" forall xs. concat xs =
     build (\c n -> foldr (\x y -> foldr c y x) n xs)
869
-- We don't bother to turn non-fusible applications of concat back into concat
870
 #-}
871

ross's avatar
ross committed
872 873 874
-- | 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.
875
(!!)                    :: [a] -> Int -> a
Ben Gamari's avatar
Ben Gamari committed
876
#if defined(USE_REPORT_PRELUDE)
Eric Seidel's avatar
Eric Seidel committed
877 878
xs     !! n | n < 0 =  errorWithoutStackTrace "Prelude.!!: negative index"
[]     !! _         =  errorWithoutStackTrace "Prelude.!!: index too large"
879 880
(x:_)  !! 0         =  x
(_:xs) !! n         =  xs !! (n-1)
881
#else
882 883 884 885 886 887

-- 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
Eric Seidel's avatar
Eric Seidel committed
888
tooLarge _ = errorWithoutStackTrace (prel_list_str ++ "!!: index too large")
889 890

negIndex :: a
Eric Seidel's avatar
Eric Seidel committed
891
negIndex = errorWithoutStackTrace $ prel_list_str ++ "!!: negative index"
892 893 894 895 896 897 898

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

901 902 903
--------------------------------------------------------------
-- The zip family
--------------------------------------------------------------
904

Ian Lynagh's avatar
Ian Lynagh committed
905
foldr2 :: (a -> b -> c -> c) -> c -> [a] -> [b] -> c
Joachim Breitner's avatar
Joachim Breitner committed
906 907
foldr2 k z = go
  where
908
        go []    _ys     = z
909 910
        go _xs   []      = z
        go (x:xs) (y:ys) = k x y (go xs ys)
911
{-# INLINE [0] foldr2 #-}  -- See Note [Fusion for foldrN]
912

Ian Lynagh's avatar
Ian Lynagh committed
913
foldr2_left :: (a -> b -> c -> d) -> d -> a -> ([b] -> c) -> [b] -> d
914 915 916 917
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
918
{-# RULES   -- See Note [Fusion for foldrN]
Jan Stolarek's avatar
Jan Stolarek committed
919
"foldr2/left"   forall k z ys (g::forall b.(a->b->b)->b->b) .
Don Stewart's avatar
Don Stewart committed
920
                  foldr2 k z (build g) ys = g (foldr2_left  k z) (\_ -> z) ys
921
 #-}
922 923 924 925 926 927 928 929

foldr3 :: (a -> b -> c -> d -> d) -> d -> [a] -> [b] -> [c] -> d
foldr3 k z = go
  where
    go  []    _      _      = z
    go  _     []     _      = z
    go  _     _      []     = z
    go (a:as) (b:bs) (c:cs) = k a b c (go as bs cs)
930
{-# INLINE [0] foldr3 #-}  -- See Note [Fusion for foldrN]
931 932 933 934 935 936 937 938


foldr3_left :: (a -> b -> c -> d -> e) -> e -> a ->
               ([b] -> [c] -> d) -> [b] -> [c] -> e
foldr3_left k _z a r (b:bs) (c:cs) = k a b c (r bs cs)
foldr3_left _  z _ _  _      _     = z

-- foldr3 k n xs ys zs = foldr (foldr3_left k n) (\_ _ -> n) xs ys zs
939
{-# RULES   -- See Note [Fusion for foldrN]
940 941 942 943
"foldr3/left"   forall k z (g::forall b.(a->b->b)->b->b).
                  foldr3 k z (build g) = g (foldr3_left k z) (\_ _ -> z)
 #-}

944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995
{- Note [Fusion for foldrN]
~~~~~~~~~~~~~~~~~~~~~~~~~~~
We arrange that foldr2, foldr3, etc is a good consumer for its first
(left) list argument. Here's how. See below for the second, third
etc list arguments

* The rule "foldr2/left" (active only before phase 1) does this:
     foldr2 k z (build g) ys = g (foldr2_left  k z) (\_ -> z) ys
  thereby fusing away the 'build' on the left argument

* To ensure this rule has a chance to fire, foldr2 has a NOINLINE[1] pragma

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):_|_

Note [Fusion for zipN/zipWithN]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
We arrange that zip, zip3, etc, and zipWith, zipWit3 etc, are all
good consumers for their first (left) argument, and good producers.
Here's how.  See Note [Fusion for foldr2] for why it can't fuse its
second (right) list argument.

NB: Zips for larger tuples are in the List module.

* Rule "zip" (active only before phase 1) rewrites
    zip xs ys = build (\c n -> foldr2 (zipFB c) n xs ys)
  See also Note [Inline FB functions]

  Ditto rule "zipWith".

* To give this rule a chance to fire, we give zip a NOLINLINE[1]
  pragma (although since zip is recursive it might not need it)

* Now the rules for foldr2 (see Note [Fusion for foldr2]) may fire,
  or rules that fuse the build-produced output of zip.

* If none of these fire, rule "zipList" (active only in phase 1)
  rewrites the foldr2 call back to zip
     foldr2 (zipFB (:)) []   = zip
  This rule will only fire when build has inlined, which also
  happens in phase 1.

  Ditto rule "zipWithList".
-}
996

997
----------------------------------------------
998
-- | \(\mathcal{O}(\min(m,n))\). 'zip' takes two lists and returns a list of
999
-- corresponding pairs.
taylorfausak's avatar
taylorfausak committed
1000 1001 1002
--
-- > zip [1, 2] ['a', 'b'] = [(1, 'a'), (2, 'b')]
--
ross's avatar
ross committed
1003
-- If one input list is short, excess elements of the longer list are
taylorfausak's avatar
taylorfausak committed
1004 1005 1006 1007
-- discarded:
--
-- > zip [1] ['a', 'b'] = [(1, 'a')]
-- > zip [1, 2] ['a'] = [(1, 'a')]
David Feuer's avatar
David Feuer committed
1008
--
1009 1010 1011
-- 'zip' is right-lazy:
--
-- > zip [] _|_ = []
taylorfausak's avatar
taylorfausak committed
1012
-- > zip _|_ [] = _|_
1013 1014 1015
--
-- 'zip' is capable of list fusion, but it is restricted to its
-- first list argument and its resulting list.
1016
{-# NOINLINE [1] zip #-}  -- See Note [Fusion for zipN/zipWithN]
1017
zip :: [a] -> [b] -> [(a,b)]
1018
zip []     _bs    = []
David Feuer's avatar
David Feuer committed
1019
zip _as    []     = []
1020
zip (a:as) (b:bs) = (a,b) : zip as bs
1021

1022
{-# INLINE [0] zipFB #-} -- See Note [Inline FB functions]
Ian Lynagh's avatar
Ian Lynagh committed
1023
zipFB :: ((a, b) -> c -> d) -> a -> b -> c -> d
1024
zipFB c = \x y r -> (x,y) `c` r
1025

1026
{-# RULES  -- See Note [Fusion for zipN/zipWithN]
Don Stewart's avatar
Don Stewart committed
1027 1028
"zip"      [~1] forall xs ys. zip xs ys = build (\c n -> foldr2 (zipFB c) n xs ys)
"zipList"  [1]  foldr2 (zipFB (:)) []   = zip
1029 1030 1031
 #-}

----------------------------------------------
ross's avatar
ross committed
1032 1033
-- | 'zip3' takes three lists and returns a list of triples, analogous to
-- 'zip'.
1034 1035 1036
-- It is capable of list fusion, but it is restricted to its
-- first list argument and its resulting list.
{-# NOINLINE [1] zip3 #-}
1037 1038 1039 1040 1041 1042
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 _      _      _      = []

1043 1044 1045 1046
{-# INLINE [0] zip3FB #-} -- See Note [Inline FB functions]
zip3FB :: ((a,b,c) -> xs -> xs') -> a -> b -> c -> xs -> xs'
zip3FB cons = \a b c r -> (a,b,c) `cons` r

1047
{-# RULES    -- See Note [Fusion for zipN/zipWithN]
1048 1049 1050
"zip3"       [~1] forall as bs cs. zip3 as bs cs = build (\c n -> foldr3 (zip3FB c) n as bs cs)
"zip3List"   [1]          foldr3 (zip3FB (:)) [] = zip3
 #-}
1051 1052 1053 1054 1055

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

----------------------------------------------
1056
-- | \(\mathcal{O}(\min(m,n))\). 'zipWith' generalises 'zip' by zipping with the
1057 1058 1059
-- 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:
1060 1061 1062
--
-- >>> zipWith (+) [1, 2, 3] [4, 5, 6]
-- [5,7,9]
David Feuer's avatar
David Feuer committed
1063
--
1064 1065 1066
-- 'zipWith' is right-lazy:
--
-- > zipWith f [] _|_ = []
1067 1068 1069
--
-- 'zipWith' is capable of list fusion, but it is restricted to its
-- first list argument and its resulting list.
1070
{-# NOINLINE [1] zipWith #-}  -- See Note [Fusion for zipN/zipWithN]
1071
zipWith :: (a->b->c) -> [a]->[b]->[c]
Tao He's avatar
Tao He committed
1072 1073 1074 1075