List.hs 37.7 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
-- | /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
-- | /O(1)/. Decompose a list into its head and tail. If the list is empty,
David Feuer's avatar
David Feuer committed
66 67
-- returns 'Nothing'. If the list is non-empty, returns @'Just' (x, xs)@,
-- 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
-- | /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
-- | /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
-- | /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
-- | /O(1)/. Test whether a list is empty.
115 116 117 118
null                    :: [a] -> Bool
null []                 =  True
null (_:_)              =  False

119
-- | /O(n)/. 'length' returns the length of a finite list as an 'Int'.
ross's avatar
ross committed
120 121
-- 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
-- | /O(n)/. 'filter', applied to a predicate and a list, returns the list of
ross's avatar
ross committed
146 147 148
-- those elements that satisfy the predicate; i.e.,
--
-- > 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 229 230 231
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
allocation-free. Also see Trac #13001.
-}

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

ross's avatar
ross committed
265 266 267 268 269 270 271 272 273
-- | '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
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

ross's avatar
ross committed
303 304 305 306
-- | '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
307 308 309
scanl1                  :: (a -> a -> a) -> [a] -> [a]
scanl1 f (x:xs)         =  scanl f x xs
scanl1 _ []             =  []
310

David Feuer's avatar
David Feuer committed
311 312 313 314 315 316 317 318
-- | 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]
319 320 321
    scanlGo' f !q ls    = q : (case ls of
                            []   -> []
                            x:xs -> scanlGo' f (f q x) xs)
David Feuer's avatar
David Feuer committed
322 323 324 325 326 327 328 329 330

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

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

{-# INLINE [0] flipSeqScanl' #-}
flipSeqScanl' :: a -> b -> a
338
flipSeqScanl' a !_b = a
David Feuer's avatar
David Feuer committed
339 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

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

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

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

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

ross's avatar
ross committed
383 384 385 386
-- | 'scanr' is the right-to-left dual of 'scanl'.
-- Note that
--
-- > head (scanr f z xs) == foldr f z xs.
387
{-# NOINLINE [1] scanr #-}
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 395 396 397
{-# INLINE [0] strictUncurryScanr #-}
strictUncurryScanr :: (a -> b -> c) -> (a, b) -> c
strictUncurryScanr f pair = case pair of
                              (x, y) -> f x y

398
{-# INLINE [0] scanrFB #-} -- See Note [Inline FB functions]
399 400 401 402 403 404 405 406 407 408 409
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
410
-- | 'scanr1' is a variant of 'scanr' that has no starting value argument.
411
scanr1                  :: (a -> a -> a) -> [a] -> [a]
Ian Lynagh's avatar
Ian Lynagh committed
412 413
scanr1 _ []             =  []
scanr1 _ [x]            =  [x]
Don Stewart's avatar
Don Stewart committed
414
scanr1 f (x:xs)         =  f x q : qs
Jan Stolarek's avatar
Jan Stolarek committed
415
                           where qs@(q:_) = scanr1 f xs
416

417 418 419 420 421
-- | '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
422
{-# INLINABLE maximum #-}
423 424 425
maximum []              =  errorEmptyList "maximum"
maximum xs              =  foldl1 max xs

426 427 428 429 430
-- 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 #-}
431 432 433 434 435 436

-- | '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
437
{-# INLINABLE minimum #-}
438 439 440
minimum []              =  errorEmptyList "minimum"
minimum xs              =  foldl1 min xs

441 442
{-# SPECIALIZE  minimum :: [Int] -> Int #-}
{-# SPECIALIZE  minimum :: [Integer] -> Integer #-}
443 444


ross's avatar
ross committed
445 446 447 448
-- | '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
449 450
--
-- Note that 'iterate' is lazy, potentially leading to thunk build-up if
David Sanders's avatar
David Sanders committed
451
-- the consumer doesn't force each iterate. See 'iterate'' for a strict
Ben Gamari's avatar
Ben Gamari committed
452
-- variant of this function.
453
{-# NOINLINE [1] iterate #-}
454
iterate :: (a -> a) -> a -> [a]
455
iterate f x =  x : iterate f (f x)
456

457
{-# INLINE [0] iterateFB #-} -- See Note [Inline FB functions]
Ian Lynagh's avatar
Ian Lynagh committed
458
iterateFB :: (a -> b -> b) -> (a -> a) -> a -> b
Joachim Breitner's avatar
Joachim Breitner committed
459 460
iterateFB c f x0 = go x0
  where go x = x `c` go (f x)
461 462

{-# RULES
Don Stewart's avatar
Don Stewart committed
463 464
"iterate"    [~1] forall f x.   iterate f x = build (\c _n -> iterateFB c f x)
"iterateFB"  [1]                iterateFB (:) = iterate
465 466 467
 #-}


David Sanders's avatar
David Sanders committed
468
-- | 'iterate'' is the strict version of 'iterate'.
Ben Gamari's avatar
Ben Gamari committed
469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490
--
-- 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
491
-- | 'repeat' @x@ is an infinite list, with @x@ the value of every element.
492
repeat :: a -> [a]
493 494 495
{-# INLINE [0] repeat #-}
-- The pragma just gives the rules more chance to fire
repeat x = xs where xs = x : xs
496

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

501 502

{-# RULES
503
"repeat"    [~1] forall x. repeat x = build (\c _n -> repeatFB c x)
Don Stewart's avatar
Don Stewart committed
504
"repeatFB"  [1]  repeatFB (:)       = repeat
505 506
 #-}

ross's avatar
ross committed
507 508 509 510
-- | '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.
511
{-# INLINE replicate #-}
512 513 514
replicate               :: Int -> a -> [a]
replicate n x           =  take n (repeat x)

ross's avatar
ross committed
515
-- | 'cycle' ties a finite list into a circular one, or equivalently,
516 517 518 519
-- the infinite repetition of the original list.  It is the identity
-- on infinite lists.

cycle                   :: [a] -> [a]
520
cycle []                = errorEmptyList "cycle"
Don Stewart's avatar
Don Stewart committed
521
cycle xs                = xs' where xs' = xs ++ xs'
522

ross's avatar
ross committed
523
-- | 'takeWhile', applied to a predicate @p@ and a list @xs@, returns the
524 525 526 527 528 529
-- 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] == []
--
530

531
{-# NOINLINE [1] takeWhile #-}
532 533
takeWhile               :: (a -> Bool) -> [a] -> [a]
takeWhile _ []          =  []
Jan Stolarek's avatar
Jan Stolarek committed
534
takeWhile p (x:xs)
535 536 537
            | p x       =  x : takeWhile p xs
            | otherwise =  []

538
{-# INLINE [0] takeWhileFB #-} -- See Note [Inline FB functions]
539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556
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
 #-}

557 558 559 560 561 562
-- | '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
563

564 565 566 567 568 569
dropWhile               :: (a -> Bool) -> [a] -> [a]
dropWhile _ []          =  []
dropWhile p xs@(x:xs')
            | p x       =  dropWhile p xs'
            | otherwise =  xs

ross's avatar
ross committed
570
-- | 'take' @n@, applied to a list @xs@, returns the prefix of @xs@
571 572 573 574 575 576 577 578 579
-- 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
580 581
-- It is an instance of the more general 'Data.List.genericTake',
-- in which @n@ may be of any integral type.
582
take                   :: Int -> [a] -> [a]
Ben Gamari's avatar
Ben Gamari committed
583
#if defined(USE_REPORT_PRELUDE)
584
take n _      | n <= 0 =  []
585
take _ []              =  []
586
take n (x:xs)          =  x : take (n-1) xs
587
#else
588 589 590 591 592 593 594

{- 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 #-}
595 596 597 598
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
599
-- than 1.
600 601
{-# NOINLINE [1] unsafeTake #-}
unsafeTake :: Int -> [a] -> [a]
602 603 604
unsafeTake !_  []     = []
unsafeTake 1   (x: _) = [x]
unsafeTake m   (x:xs) = x : unsafeTake (m - 1) xs
605

606
{-# RULES
607 608 609 610
"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)
611 612
"unsafeTakeList"  [1] forall n xs . foldr (takeFB (:) []) (flipSeqTake []) xs n
                                        = unsafeTake n xs
613 614
 #-}

615 616 617 618
{-# 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
619 620
-- bad for strictness analysis and unboxing, and leads to increased
-- allocation in T7257.
621 622
flipSeqTake :: a -> Int -> a
flipSeqTake x !_n = x
623

624
{-# INLINE [0] takeFB #-} -- See Note [Inline FB functions]
625
takeFB :: (a -> b -> b) -> b -> a -> (Int -> b) -> Int -> b
626 627 628 629 630 631
-- 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
632 633 634 635
  = \ m -> case m of
            1 -> x `c` n
            _ -> x `c` xs (m - 1)
#endif
636 637 638 639 640 641 642 643 644 645 646 647 648 649

-- | '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
650
#if defined(USE_REPORT_PRELUDE)
651 652 653 654 655 656 657 658 659 660 661 662
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]
663 664 665
    unsafeDrop !_ []     = []
    unsafeDrop 1  (_:xs) = xs
    unsafeDrop m  (_:xs) = unsafeDrop (m - 1) xs
666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683
#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])
684

Ben Gamari's avatar
Ben Gamari committed
685
#if defined(USE_REPORT_PRELUDE)
686 687
splitAt n xs           =  (take n xs, drop n xs)
#else
688 689 690
splitAt n ls
  | n <= 0 = ([], ls)
  | otherwise          = splitAt' n ls
691
    where
692 693 694 695
        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
696
          where
697
            (xs', xs'') = splitAt' (m - 1) xs
698 699
#endif /* USE_REPORT_PRELUDE */

700 701 702
-- | '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
703
--
704 705 706
-- > 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
707
--
708
-- 'span' @p xs@ is equivalent to @('takeWhile' p xs, 'dropWhile' p xs)@
ross's avatar
ross committed
709 710

span                    :: (a -> Bool) -> [a] -> ([a],[a])
711 712 713 714 715
span _ xs@[]            =  (xs, xs)
span p xs@(x:xs')
         | p x          =  let (ys,zs) = span p xs' in (x:ys,zs)
         | otherwise    =  ([],xs)

716 717 718
-- | '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
719
--
720 721 722 723 724
-- > 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
725 726

break                   :: (a -> Bool) -> [a] -> ([a],[a])
Ben Gamari's avatar
Ben Gamari committed
727
#if defined(USE_REPORT_PRELUDE)
728 729 730
break p                 =  span (not . p)
#else
-- HBC version (stolen)
Don Stewart's avatar
Don Stewart committed
731
break _ xs@[]           =  (xs, xs)
732
break p xs@(x:xs')
Don Stewart's avatar
Don Stewart committed
733 734
           | p x        =  ([],xs)
           | otherwise  =  let (ys,zs) = break p xs' in (x:ys,zs)
735 736
#endif

ross's avatar
ross committed
737 738
-- | 'reverse' @xs@ returns the elements of @xs@ in reverse order.
-- @xs@ must be finite.
739
reverse                 :: [a] -> [a]
Ben Gamari's avatar
Ben Gamari committed
740
#if defined(USE_REPORT_PRELUDE)
741 742 743 744 745 746 747 748
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
749 750 751 752
-- | '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
753
#if defined(USE_REPORT_PRELUDE)
754 755 756 757 758 759 760 761 762 763 764
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
765 766 767 768 769

-- | '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
770
#if defined(USE_REPORT_PRELUDE)
771 772
or                      =  foldr (||) False
#else
Don Stewart's avatar
Don Stewart committed
773 774
or []           =  False
or (x:xs)       =  x || or xs
775 776
{-# NOINLINE [1] or #-}

777
{-# RULES
Jan Stolarek's avatar
Jan Stolarek committed
778
"or/build"      forall (g::forall b.(Bool->b->b)->b->b) .
Don Stewart's avatar
Don Stewart committed
779
                or (build g) = g (||) False
780 781 782
 #-}
#endif

ross's avatar
ross committed
783
-- | Applied to a predicate and a list, 'any' determines if any element
784 785 786
-- 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
787 788
any                     :: (a -> Bool) -> [a] -> Bool

Ben Gamari's avatar
Ben Gamari committed
789
#if defined(USE_REPORT_PRELUDE)
790 791 792 793 794 795 796 797 798 799 800 801 802
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
803
-- | Applied to a predicate and a list, 'all' determines if all elements
804 805 806
-- 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
807
all                     :: (a -> Bool) -> [a] -> Bool
Ben Gamari's avatar
Ben Gamari committed
808
#if defined(USE_REPORT_PRELUDE)
809 810
all p                   =  and . map p
#else
Don Stewart's avatar
Don Stewart committed
811 812
all _ []        =  True
all p (x:xs)    =  p x && all p xs
813 814 815

{-# NOINLINE [1] all #-}

816
{-# RULES
Jan Stolarek's avatar
Jan Stolarek committed
817
"all/build"     forall p (g::forall b.(a->b->b)->b->b) .
Don Stewart's avatar
Don Stewart committed
818
                all p (build g) = g ((&&) . p) True
819 820 821
 #-}
#endif

ross's avatar
ross committed
822
-- | 'elem' is the list membership predicate, usually written in infix form,
823
-- e.g., @x \`elem\` xs@.  For the result to be
824 825
-- '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
826
elem                    :: (Eq a) => a -> [a] -> Bool
Ben Gamari's avatar
Ben Gamari committed
827
#if defined(USE_REPORT_PRELUDE)
828 829
elem x                  =  any (== x)
#else
Don Stewart's avatar
Don Stewart committed
830 831
elem _ []       = False
elem x (y:ys)   = x==y || elem x ys
832 833 834 835 836 837
{-# 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
838

839 840
-- | 'notElem' is the negation of 'elem'.
notElem                 :: (Eq a) => a -> [a] -> Bool
Ben Gamari's avatar
Ben Gamari committed
841
#if defined(USE_REPORT_PRELUDE)
842 843
notElem x               =  all (/= x)
#else
Don Stewart's avatar
Don Stewart committed
844
notElem _ []    =  True
845
notElem x (y:ys)=  x /= y && notElem x ys
846 847 848 849 850
{-# 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
 #-}
851 852
#endif

853 854 855 856
-- | /O(n)/. 'lookup' @key assocs@ looks up a key in an association list.
--
-- >>> lookup 2 [(1, "first"), (2, "second"), (3, "third")]
-- Just "second"
857 858 859
lookup                  :: (Eq a) => a -> [(a,b)] -> Maybe b
lookup _key []          =  Nothing
lookup  key ((x,y):xys)
860
    | key == x           =  Just y
861 862
    | otherwise         =  lookup key xys

ross's avatar
ross committed
863
-- | Map a function over a list and concatenate the results.
864 865 866
concatMap               :: (a -> [b]) -> [a] -> [b]
concatMap f             =  foldr ((++) . f) []

867 868 869 870 871 872 873 874
{-# 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
875
-- | Concatenate a list of lists.
876 877 878
concat :: [[a]] -> [a]
concat = foldr (++) []

879 880
{-# NOINLINE [1] concat #-}

881
{-# RULES
882 883
  "concat" forall xs. concat xs =
     build (\c n -> foldr (\x y -> foldr c y x) n xs)
884
-- We don't bother to turn non-fusible applications of concat back into concat
885
 #-}
886

ross's avatar
ross committed
887 888 889
-- | 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.
890
(!!)                    :: [a] -> Int -> a
Ben Gamari's avatar
Ben Gamari committed
891
#if defined(USE_REPORT_PRELUDE)
Eric Seidel's avatar
Eric Seidel committed
892 893
xs     !! n | n < 0 =  errorWithoutStackTrace "Prelude.!!: negative index"
[]     !! _         =  errorWithoutStackTrace "Prelude.!!: index too large"
894 895
(x:_)  !! 0         =  x
(_:xs) !! n         =  xs !! (n-1)
896
#else
897 898 899 900 901 902

-- 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
903
tooLarge _ = errorWithoutStackTrace (prel_list_str ++ "!!: index too large")
904 905

negIndex :: a
Eric Seidel's avatar
Eric Seidel committed
906
negIndex = errorWithoutStackTrace $ prel_list_str ++ "!!: negative index"
907 908 909 910 911 912 913

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

916 917 918
--------------------------------------------------------------
-- The zip family
--------------------------------------------------------------
919

Ian Lynagh's avatar
Ian Lynagh committed
920
foldr2 :: (a -> b -> c -> c) -> c -> [a] -> [b] -> c
Joachim Breitner's avatar
Joachim Breitner committed
921 922
foldr2 k z = go
  where
923
        go []    _ys     = z
924 925
        go _xs   []      = z
        go (x:xs) (y:ys) = k x y (go xs ys)
Joachim Breitner's avatar
Joachim Breitner committed
926
{-# INLINE [0] foldr2 #-}
927

Ian Lynagh's avatar
Ian Lynagh committed
928
foldr2_left :: (a -> b -> c -> d) -> d -> a -> ([b] -> c) -> [b] -> d
929 930 931 932 933
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
934
"foldr2/left"   forall k z ys (g::forall b.(a->b->b)->b->b) .
Don Stewart's avatar
Don Stewart committed
935
                  foldr2 k z (build g) ys = g (foldr2_left  k z) (\_ -> z) ys
936
 #-}
937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958

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)
{-# INLINE [0] foldr3 #-}


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
{-# RULES
"foldr3/left"   forall k z (g::forall b.(a->b->b)->b->b).
                  foldr3 k z (build g) = g (foldr3_left k z) (\_ _ -> z)
 #-}

959 960 961 962 963 964 965 966 967 968 969 970 971 972 973
-- 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):_|_
974

975 976
-- Zips for larger tuples are in the List module.

977
----------------------------------------------
ross's avatar
ross committed
978
-- | 'zip' takes two lists and returns a list of corresponding pairs.
taylorfausak's avatar
taylorfausak committed
979 980 981
--
-- > zip [1, 2] ['a', 'b'] = [(1, 'a'), (2, 'b')]
--
ross's avatar
ross committed
982
-- If one input list is short, excess elements of the longer list are
taylorfausak's avatar
taylorfausak committed
983 984 985 986
-- discarded:
--
-- > zip [1] ['a', 'b'] = [(1, 'a')]
-- > zip [1, 2] ['a'] = [(1, 'a')]
David Feuer's avatar
David Feuer committed
987
--
988 989 990
-- 'zip' is right-lazy:
--
-- > zip [] _|_ = []
taylorfausak's avatar
taylorfausak committed
991
-- > zip _|_ [] = _|_
992 993 994
--
-- 'zip' is capable of list fusion, but it is restricted to its
-- first list argument and its resulting list.
995
{-# NOINLINE [1] zip #-}
996
zip :: [a] -> [b] -> [(a,b)]
997
zip []     _bs    = []
David Feuer's avatar
David Feuer committed
998
zip _as    []     = []
999
zip (a:as) (b:bs) = (a,b) : zip as bs
1000

1001
{-# INLINE [0] zipFB #-} -- See Note [Inline FB functions]
Ian Lynagh's avatar
Ian Lynagh committed
1002
zipFB :: ((a, b) -> c -> d) -> a -> b -> c -> d
1003
zipFB c = \x y r -> (x,y) `c` r
1004 1005

{-# RULES
Don Stewart's avatar
Don Stewart committed
1006 1007
"zip"      [~1] forall xs ys. zip xs ys = build (\c n -> foldr2 (zipFB c) n xs ys)
"zipList"  [1]  foldr2 (zipFB (:)) []   = zip
1008 1009 1010
 #-}

----------------------------------------------
ross's avatar
ross committed
1011 1012
-- | 'zip3' takes three lists and returns a list of triples, analogous to
-- 'zip'.
1013 1014 1015
-- It is capable of list fusion, but it is restricted to its
-- first list argument and its resulting list.
{-# NOINLINE [1] zip3 #-}
1016 1017 1018 1019 1020 1021
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 _      _      _      = []

1022 1023 1024 1025 1026 1027 1028 1029
{-# 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

{-# RULES
"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
 #-}