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

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

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

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

 ) where

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

228 229 230 231 232 233
-- ----------------------------------------------------------------------------

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

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

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

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

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

298

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


ross's avatar
ross committed
441 442 443 444 445
-- | 'iterate' @f x@ returns an infinite list of repeated applications
-- of @f@ to @x@:
--
-- > iterate f x == [x, f x, f (f x), ...]

446
{-# NOINLINE [1] iterate #-}
447
iterate :: (a -> a) -> a -> [a]
448
iterate f x =  x : iterate f (f x)
449

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

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


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

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

494 495

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

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

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

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

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

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

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

550 551 552 553 554 555
-- | '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
556

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{-# NOINLINE [1] all #-}

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

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

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

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

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

869 870
{-# NOINLINE [1] concat #-}

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

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

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

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

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

906 907 908
--------------------------------------------------------------
-- The zip family
--------------------------------------------------------------
909

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

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

943 944
-- Zips for larger tuples are in the List module.

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

959
{-# INLINE [0] zipFB #-} -- See Note [Inline FB functions]
Ian Lynagh's avatar
Ian Lynagh committed
960
zipFB :: ((a, b) -> c -> d) -> a -> b -> c -> d
961
zipFB c = \x y r -> (x,y) `c` r
962 963

{-# RULES
Don Stewart's avatar
Don Stewart committed
964 965
"zip"      [~1] forall xs ys. zip xs ys = build (\c n -> foldr2 (zipFB c) n xs ys)
"zipList"  [1]  foldr2 (zipFB (:)) []   = zip
966 967 968
 #-}

----------------------------------------------
ross's avatar
ross committed
969 970
-- | 'zip3' takes three lists and returns a list of triples, analogous to
-- 'zip'.
971 972 973 974 975 976 977 978 979 980 981
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
982 983 984 985
-- | '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
986
--
987 988 989
-- 'zipWith' is right-lazy:
--
-- > zipWith f [] _|_ = []
990
{-# NOINLINE [1] zipWith #-}
991
zipWith :: (a->b->c) -> [a]->[b]->[c]
992
zipWith _f []     _bs    = []
David Feuer's avatar
David Feuer committed
993 994
zipWith _f _as    []     = []
zipWith f  (a:as) (b:bs) = f a b : zipWith f as bs
995

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

{-# RULES
Don Stewart's avatar
Don Stewart committed
1003 1004
"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
1005 1006
  #-}

ross's avatar
ross committed
1007 1008 1009
-- | 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'.
1010 1011 1012 1013 1014
zipWith3                :: (a->b->c->d) -> [a]->[b]->[c]->[d]
zipWith3 z (a:as) (b:bs) (c:cs)
                        =  z a b c : zipWith3 z as bs cs
zipWith3 _ _ _ _        =  []

ross's avatar
ross committed
1015 1016
-- | 'unzip' transforms a list of pairs into a list of first components
-- and a list of second components.
1017 1018 1019 1020
unzip    :: [(a,b)] -> ([a],[b])
{-# INLINE unzip #-}
unzip    =  foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])

ross's avatar
ross committed
1021 1022
-- | The 'unzip3' function takes a list of triples and returns three
-- lists, analogous to 'unzip'.
1023