List.hs 35.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

ross's avatar
ross committed
47
-- | 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
 #-}

David Feuer's avatar
David Feuer committed
65 66 67
-- | 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.
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)

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

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

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

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

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

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

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

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

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

ross's avatar
ross committed
143 144 145 146 147
-- | '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]

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

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

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

-- 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
176 177 178 179 180 181 182
-- | '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.
183

Joachim Breitner's avatar
Joachim Breitner committed
184 185
foldl :: forall a b. (b -> a -> b) -> b -> [a] -> b
{-# INLINE foldl #-}
186
foldl k z0 xs =
187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204
  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
205
arguments to foldr, where we know how the arguments are called.
206

207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226
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.
-}

227 228 229 230 231 232
-- ----------------------------------------------------------------------------

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

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

ross's avatar
ross committed
260 261 262 263 264 265 266 267 268
-- | '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
269 270 271
-- This peculiar arrangement is necessary to prevent scanl being rewritten in
-- its own right-hand side.
{-# NOINLINE [1] scanl #-}
272
scanl                   :: (b -> a -> b) -> b -> [a] -> [b]
David Feuer's avatar
David Feuer committed
273 274 275 276 277 278 279 280 281 282 283 284 285 286 287
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)
 #-}

288
{-# INLINE [0] scanlFB #-} -- See Note [Inline FB functions]
David Feuer's avatar
David Feuer committed
289
scanlFB :: (b -> a -> b) -> (b -> c -> c) -> a -> (b -> c) -> b -> c
290 291
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
292 293 294 295 296

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

297

ross's avatar
ross committed
298 299 300 301
-- | '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
302 303 304
scanl1                  :: (a -> a -> a) -> [a] -> [a]
scanl1 f (x:xs)         =  scanl f x xs
scanl1 _ []             =  []
305

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

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

326
{-# INLINE [0] scanlFB' #-} -- See Note [Inline FB functions]
David Feuer's avatar
David Feuer committed
327
scanlFB' :: (b -> a -> b) -> (b -> c -> c) -> a -> (b -> c) -> b -> c
328 329
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
330 331 332

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

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

365 366 367
-- foldr, foldr1, scanr, and scanr1 are the right-to-left duals of the
-- above functions.

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

371
foldr1                  :: (a -> a -> a) -> [a] -> a
372 373 374 375 376
foldr1 f = go
  where go [x]            =  x
        go (x:xs)         =  f x (go xs)
        go []             =  errorEmptyList "foldr1"
{-# INLINE [0] foldr1 #-}
377

ross's avatar
ross committed
378 379 380 381
-- | 'scanr' is the right-to-left dual of 'scanl'.
-- Note that
--
-- > head (scanr f z xs) == foldr f z xs.
382
{-# NOINLINE [1] scanr #-}
383 384 385
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
386
                           where qs@(q:_) = scanr f q0 xs
387

388 389 390 391 392
{-# INLINE [0] strictUncurryScanr #-}
strictUncurryScanr :: (a -> b -> c) -> (a, b) -> c
strictUncurryScanr f pair = case pair of
                              (x, y) -> f x y

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

412 413 414 415 416
-- | '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
417
{-# INLINABLE maximum #-}
418 419 420
maximum []              =  errorEmptyList "maximum"
maximum xs              =  foldl1 max xs

421 422 423 424 425
-- 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 #-}
426 427 428 429 430 431

-- | '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
432
{-# INLINABLE minimum #-}
433 434 435
minimum []              =  errorEmptyList "minimum"
minimum xs              =  foldl1 min xs

436 437
{-# SPECIALIZE  minimum :: [Int] -> Int #-}
{-# SPECIALIZE  minimum :: [Integer] -> Integer #-}
438 439


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

452
{-# INLINE [0] iterateFB #-} -- See Note [Inline FB functions]
Ian Lynagh's avatar
Ian Lynagh committed
453
iterateFB :: (a -> b -> b) -> (a -> a) -> a -> b
Joachim Breitner's avatar
Joachim Breitner committed
454 455
iterateFB c f x0 = go x0
  where go x = x `c` go (f x)
456 457

{-# RULES
Don Stewart's avatar
Don Stewart committed
458 459
"iterate"    [~1] forall f x.   iterate f x = build (\c _n -> iterateFB c f x)
"iterateFB"  [1]                iterateFB (:) = iterate
460 461 462
 #-}


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

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

496 497

{-# RULES
498
"repeat"    [~1] forall x. repeat x = build (\c _n -> repeatFB c x)
Don Stewart's avatar
Don Stewart committed
499
"repeatFB"  [1]  repeatFB (:)       = repeat
500 501
 #-}

ross's avatar
ross committed
502 503 504 505
-- | '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.
506
{-# INLINE replicate #-}
507 508 509
replicate               :: Int -> a -> [a]
replicate n x           =  take n (repeat x)

ross's avatar
ross committed
510
-- | 'cycle' ties a finite list into a circular one, or equivalently,
511 512 513 514
-- the infinite repetition of the original list.  It is the identity
-- on infinite lists.

cycle                   :: [a] -> [a]
515
cycle []                = errorEmptyList "cycle"
Don Stewart's avatar
Don Stewart committed
516
cycle xs                = xs' where xs' = xs ++ xs'
517

ross's avatar
ross committed
518
-- | 'takeWhile', applied to a predicate @p@ and a list @xs@, returns the
519 520 521 522 523 524
-- 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] == []
--
525

526
{-# NOINLINE [1] takeWhile #-}
527 528
takeWhile               :: (a -> Bool) -> [a] -> [a]
takeWhile _ []          =  []
Jan Stolarek's avatar
Jan Stolarek committed
529
takeWhile p (x:xs)
530 531 532
            | p x       =  x : takeWhile p xs
            | otherwise =  []

533
{-# INLINE [0] takeWhileFB #-} -- See Note [Inline FB functions]
534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551
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
 #-}

552 553 554 555 556 557
-- | '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
558

559 560 561 562 563 564
dropWhile               :: (a -> Bool) -> [a] -> [a]
dropWhile _ []          =  []
dropWhile p xs@(x:xs')
            | p x       =  dropWhile p xs'
            | otherwise =  xs

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

{- 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 #-}
590 591 592 593
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
594
-- than 1.
595 596
{-# NOINLINE [1] unsafeTake #-}
unsafeTake :: Int -> [a] -> [a]
597 598 599
unsafeTake !_  []     = []
unsafeTake 1   (x: _) = [x]
unsafeTake m   (x:xs) = x : unsafeTake (m - 1) xs
600

601
{-# RULES
602 603 604 605
"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)
606 607
"unsafeTakeList"  [1] forall n xs . foldr (takeFB (:) []) (flipSeqTake []) xs n
                                        = unsafeTake n xs
608 609
 #-}

610 611 612 613
{-# 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
614 615
-- bad for strictness analysis and unboxing, and leads to increased
-- allocation in T7257.
616 617
flipSeqTake :: a -> Int -> a
flipSeqTake x !_n = x
618

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

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

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

695 696 697
-- | '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
698
--
699 700 701
-- > 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
702
--
703
-- 'span' @p xs@ is equivalent to @('takeWhile' p xs, 'dropWhile' p xs)@
ross's avatar
ross committed
704 705

span                    :: (a -> Bool) -> [a] -> ([a],[a])
706 707 708 709 710
span _ xs@[]            =  (xs, xs)
span p xs@(x:xs')
         | p x          =  let (ys,zs) = span p xs' in (x:ys,zs)
         | otherwise    =  ([],xs)

711 712 713
-- | '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
714
--
715 716 717 718 719
-- > 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
720 721

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

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

-- | '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
765
#if defined(USE_REPORT_PRELUDE)
766 767
or                      =  foldr (||) False
#else
Don Stewart's avatar
Don Stewart committed
768 769
or []           =  False
or (x:xs)       =  x || or xs
770 771
{-# NOINLINE [1] or #-}

772
{-# RULES
Jan Stolarek's avatar
Jan Stolarek committed
773
"or/build"      forall (g::forall b.(Bool->b->b)->b->b) .
Don Stewart's avatar
Don Stewart committed
774
                or (build g) = g (||) False
775 776 777
 #-}
#endif

ross's avatar
ross committed
778
-- | Applied to a predicate and a list, 'any' determines if any element
779 780 781
-- 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
782 783
any                     :: (a -> Bool) -> [a] -> Bool

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

{-# NOINLINE [1] all #-}

811
{-# RULES
Jan Stolarek's avatar
Jan Stolarek committed
812
"all/build"     forall p (g::forall b.(a->b->b)->b->b) .
Don Stewart's avatar
Don Stewart committed
813
                all p (build g) = g ((&&) . p) True
814 815 816
 #-}
#endif

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

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

ross's avatar
ross committed
848
-- | 'lookup' @key assocs@ looks up a key in an association list.
849 850 851 852 853 854
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
855
-- | Map a function over a list and concatenate the results.
856 857 858
concatMap               :: (a -> [b]) -> [a] -> [b]
concatMap f             =  foldr ((++) . f) []

859 860 861 862 863 864 865 866
{-# 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
867
-- | Concatenate a list of lists.
868 869 870
concat :: [[a]] -> [a]
concat = foldr (++) []

871 872
{-# NOINLINE [1] concat #-}

873
{-# RULES
874 875
  "concat" forall xs. concat xs =
     build (\c n -> foldr (\x y -> foldr c y x) n xs)
876
-- We don't bother to turn non-fusible applications of concat back into concat
877
 #-}
878

ross's avatar
ross committed
879 880 881
-- | 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.
882
(!!)                    :: [a] -> Int -> a
Ben Gamari's avatar
Ben Gamari committed
883
#if defined(USE_REPORT_PRELUDE)
Eric Seidel's avatar
Eric Seidel committed
884 885
xs     !! n | n < 0 =  errorWithoutStackTrace "Prelude.!!: negative index"
[]     !! _         =  errorWithoutStackTrace "Prelude.!!: index too large"
886 887
(x:_)  !! 0         =  x
(_:xs) !! n         =  xs !! (n-1)
888
#else
889 890 891 892 893 894

-- 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
895
tooLarge _ = errorWithoutStackTrace (prel_list_str ++ "!!: index too large")
896 897

negIndex :: a
Eric Seidel's avatar
Eric Seidel committed
898
negIndex = errorWithoutStackTrace $ prel_list_str ++ "!!: negative index"
899 900 901 902 903 904 905

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

908 909 910
--------------------------------------------------------------
-- The zip family
--------------------------------------------------------------
911

Ian Lynagh's avatar
Ian Lynagh committed
912
foldr2 :: (a -> b -> c -> c) -> c -> [a] -> [b] -> c
Joachim Breitner's avatar
Joachim Breitner committed
913 914
foldr2 k z = go
  where
915
        go []    _ys     = z
916 917
        go _xs   []      = z
        go (x:xs) (y:ys) = k x y (go xs ys)
Joachim Breitner's avatar
Joachim Breitner committed
918
{-# INLINE [0] foldr2 #-}
919

Ian Lynagh's avatar
Ian Lynagh committed
920
foldr2_left :: (a -> b -> c -> d) -> d -> a -> ([b] -> c) -> [b] -> d
921 922 923 924 925
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
926
"foldr2/left"   forall k z ys (g::forall b.(a->b->b)->b->b) .
Don Stewart's avatar
Don Stewart committed
927
                  foldr2 k z (build g) ys = g (foldr2_left  k z) (\_ -> z) ys
928
 #-}
929 930 931 932 933 934 935 936 937 938 939 940 941 942 943
-- 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):_|_
944

945 946
-- Zips for larger tuples are in the List module.

947
----------------------------------------------
ross's avatar
ross committed
948
-- | 'zip' takes two lists and returns a list of corresponding pairs.
taylorfausak's avatar
taylorfausak committed
949 950 951
--
-- > zip [1, 2] ['a', 'b'] = [(1, 'a'), (2, 'b')]
--
ross's avatar
ross committed
952
-- If one input list is short, excess elements of the longer list are
taylorfausak's avatar
taylorfausak committed
953 954 955 956
-- discarded:
--
-- > zip [1] ['a', 'b'] = [(1, 'a')]
-- > zip [1, 2] ['a'] = [(1, 'a')]
David Feuer's avatar
David Feuer committed
957
--
958 959 960
-- 'zip' is right-lazy:
--
-- > zip [] _|_ = []
taylorfausak's avatar
taylorfausak committed
961
-- > zip _|_ [] = _|_
962
{-# NOINLINE [1] zip #-}
963
zip :: [a] -> [b] -> [(a,b)]
964
zip []     _bs    = []
David Feuer's avatar
David Feuer committed
965
zip _as    []     = []
966
zip (a:as) (b:bs) = (a,b) : zip as bs
967

968
{-# INLINE [0] zipFB #-} -- See Note [Inline FB functions]
Ian Lynagh's avatar
Ian Lynagh committed
969
zipFB :: ((a, b) -> c -> d) -> a -> b -> c -> d
970
zipFB c = \x y r -> (x,y) `c` r
971 972

{-# RULES
Don Stewart's avatar
Don Stewart committed
973 974
"zip"      [~1] forall xs ys. zip xs ys = build (\c n -> foldr2 (zipFB c) n xs ys)
"zipList"  [1]  foldr2 (zipFB (:)) []   = zip
975 976 977
 #-}

----------------------------------------------
ross's avatar
ross committed
978 979
-- | 'zip3' takes three lists and returns a list of triples, analogous to
-- 'zip'.
980 981 982 983 984 985 986 987 988 989 990
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
991 992 993 994
-- | '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
995
--
996 997 998
-- 'zipWith' is right-lazy:
--
-- > zipWith f [] _|_ = []
999
{-# NOINLINE [1] zipWith #-}
1000
zipWith :: (a->b->c) -> [a]->[b]->[c]
Tao He's avatar
Tao He committed
1001 1002 1003 1004 1005
zipWith f = go
  where
    go [] _ = []
    go _ [] = []
    go (x:xs) (y:ys) = f x y : go xs ys
1006

1007 1008
-- zipWithFB must have arity 2 since it gets two arguments in the "zipWith"
-- rule; it might not get inlined otherwise
1009
{-# INLINE [0] zipWithFB #-} -- See Note [Inline FB functions]
Ian Lynagh's avatar
Ian Lynagh committed
1010
zipWithFB :: (a -> b -> c) -> (d -> e -> a) -> d -> e -> b -> c
1011
zipWithFB c f = \x y r -> (x `f` y) `c` r
1012 1013

{-# RULES
Don Stewart's avatar
Don Stewart committed
1014 1015
"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
1016 1017
  #-}

ross's avatar
ross committed
1018 1019 1020
-- | 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'.