{-# LANGUAGE Trustworthy #-}
{-# LANGUAGE CPP, NoImplicitPrelude, ScopedTypeVariables, MagicHash #-}
{-# LANGUAGE BangPatterns #-}

-----------------------------------------------------------------------------
-- |
-- Module      :  GHC.List
-- Copyright   :  (c) The University of Glasgow 1994-2002
-- License     :  see libraries/base/LICENSE
--
-- Maintainer  :  cvs-ghc@haskell.org
-- Stability   :  internal
-- Portability :  non-portable (GHC Extensions)
--
-- The List data type and its operations
--
-----------------------------------------------------------------------------

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

   map, (++), filter, concat,
   head, last, tail, init, uncons, null, length, (!!),
   foldl, foldl', foldl1, foldl1', scanl, scanl1, scanl', foldr, foldr1,
   scanr, scanr1, iterate, iterate', repeat, replicate, cycle,
   take, drop, sum, product, maximum, minimum, splitAt, takeWhile, dropWhile,
   span, break, reverse, and, or,
   any, all, elem, notElem, lookup,
   concatMap,
   zip, zip3, zipWith, zipWith3, unzip, unzip3,
   errorEmptyList,

 ) where

import Data.Maybe
import GHC.Base
import GHC.Num (Num(..))
import GHC.Integer (Integer)

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

--------------------------------------------------------------
-- List-manipulation functions
--------------------------------------------------------------

-- | /O(1)/. Extract the first element of a list, which must be non-empty.
head                    :: [a] -> a
head :: [a] -> a
head (x :: a
x:_)              =  a
x
head []                 =  a
forall a. a
badHead
{-# NOINLINE [1] head #-}

badHead :: a
badHead :: a
badHead = String -> a
forall a. String -> a
errorEmptyList "head"

-- This rule is useful in cases like
--      head [y | (x,y) <- ps, x==t]
{-# RULES
"head/build"    forall (g::forall b.(a->b->b)->b->b) .
                head (build g) = g (\x _ -> x) badHead
"head/augment"  forall xs (g::forall b. (a->b->b) -> b -> b) .
                head (augment g xs) = g (\x _ -> x) (head xs)
 #-}

-- | /O(1)/. Decompose a list into its head and tail. If the list is empty,
-- returns 'Nothing'. If the list is non-empty, returns @'Just' (x, xs)@,
-- where @x@ is the head of the list and @xs@ its tail.
--
-- @since 4.8.0.0
uncons                  :: [a] -> Maybe (a, [a])
uncons :: [a] -> Maybe (a, [a])
uncons []               = Maybe (a, [a])
forall a. Maybe a
Nothing
uncons (x :: a
x:xs :: [a]
xs)           = (a, [a]) -> Maybe (a, [a])
forall a. a -> Maybe a
Just (a
x, [a]
xs)

-- | /O(1)/. Extract the elements after the head of a list, which must be
-- non-empty.
tail                    :: [a] -> [a]
tail :: [a] -> [a]
tail (_:xs :: [a]
xs)             =  [a]
xs
tail []                 =  String -> [a]
forall a. String -> a
errorEmptyList "tail"

-- | /O(n)/. Extract the last element of a list, which must be finite and
-- non-empty.
last                    :: [a] -> a
#if defined(USE_REPORT_PRELUDE)
last [x]                =  x
last (_:xs)             =  last xs
last []                 =  errorEmptyList "last"
#else
-- 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 :: [a] -> a
last xs :: [a]
xs = (a -> a -> a) -> a -> [a] -> a
forall a b. (b -> a -> b) -> b -> [a] -> b
foldl (\_ x :: a
x -> a
x) a
forall a. a
lastError [a]
xs
{-# INLINE last #-}
-- The inline pragma is required to make GHC remember the implementation via
-- foldl.
lastError :: a
lastError :: a
lastError = String -> a
forall a. String -> a
errorEmptyList "last"
#endif

-- | /O(n)/. Return all the elements of a list except the last one.
-- The list must be non-empty.
init                    :: [a] -> [a]
#if defined(USE_REPORT_PRELUDE)
init [x]                =  []
init (x:xs)             =  x : init xs
init []                 =  errorEmptyList "init"
#else
-- eliminate repeated cases
init :: [a] -> [a]
init []                 =  String -> [a]
forall a. String -> a
errorEmptyList "init"
init (x :: a
x:xs :: [a]
xs)             =  a -> [a] -> [a]
forall t. t -> [t] -> [t]
init' a
x [a]
xs
  where init' :: t -> [t] -> [t]
init' _ []     = []
        init' y :: t
y (z :: t
z:zs :: [t]
zs) = t
y t -> [t] -> [t]
forall t. t -> [t] -> [t]
: t -> [t] -> [t]
init' t
z [t]
zs
#endif

-- | /O(1)/. Test whether a list is empty.
null                    :: [a] -> Bool
null :: [a] -> Bool
null []                 =  Bool
True
null (_:_)              =  Bool
False

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

lenAcc          :: [a] -> Int -> Int
lenAcc :: [a] -> Int -> Int
lenAcc []     n :: Int
n = Int
n
lenAcc (_:ys :: [a]
ys) n :: Int
n = [a] -> Int -> Int
forall a. [a] -> Int -> Int
lenAcc [a]
ys (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
+1)

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

-- 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
lengthFB :: x -> (Int -> Int) -> Int -> Int
lengthFB _ r :: Int -> Int
r = \ !Int
a -> Int -> Int
r (Int
a Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1)

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

-- | /O(n)/. '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]
--
-- >>> filter odd [1, 2, 3]
-- [1,3]

{-# NOINLINE [1] filter #-}
filter :: (a -> Bool) -> [a] -> [a]
filter :: (a -> Bool) -> [a] -> [a]
filter _pred :: a -> Bool
_pred []    = []
filter pred :: a -> Bool
pred (x :: a
x:xs :: [a]
xs)
  | a -> Bool
pred a
x         = a
x a -> [a] -> [a]
forall t. t -> [t] -> [t]
: (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter a -> Bool
pred [a]
xs
  | Bool
otherwise      = (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter a -> Bool
pred [a]
xs

{-# INLINE [0] filterFB #-} -- See Note [Inline FB functions]
filterFB :: (a -> b -> b) -> (a -> Bool) -> a -> b -> b
filterFB :: (a -> b -> b) -> (a -> Bool) -> a -> b -> b
filterFB c :: a -> b -> b
c p :: a -> Bool
p x :: a
x r :: b
r | a -> Bool
p a
x       = a
x a -> b -> b
`c` b
r
                 | Bool
otherwise = b
r

{-# RULES
"filter"     [~1] forall p xs.  filter p xs = build (\c n -> foldr (filterFB c p) n xs)
"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)
 #-}

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


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

foldl :: forall a b. (b -> a -> b) -> b -> [a] -> b
{-# INLINE foldl #-}
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl k :: b -> a -> b
k z0 :: b
z0 xs :: [a]
xs =
  (a -> (b -> b) -> b -> b) -> (b -> b) -> [a] -> b -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
foldr (\(a
v::a) (b -> b
fn::b->b) -> (b -> b) -> b -> b
oneShot (\(b
z::b) -> b -> b
fn (b -> a -> b
k b
z a
v))) (b -> b
forall a. a -> a
id :: b -> b) [a]
xs b
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
arguments to foldr, where we know how the arguments are called.

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

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

-- | A strict version of 'foldl'.
foldl'           :: forall a b . (b -> a -> b) -> b -> [a] -> b
{-# INLINE foldl' #-}
foldl' :: (b -> a -> b) -> b -> [a] -> b
foldl' k :: b -> a -> b
k z0 :: b
z0 xs :: [a]
xs =
  (a -> (b -> b) -> b -> b) -> (b -> b) -> [a] -> b -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
foldr (\(a
v::a) (b -> b
fn::b->b) -> (b -> b) -> b -> b
oneShot (\(b
z::b) -> b
z b -> b -> b
forall a b. a -> b -> b
`seq` b -> b
fn (b -> a -> b
k b
z a
v))) (b -> b
forall a. a -> a
id :: b -> b) [a]
xs b
z0
  -- See Note [Left folds via right fold]

-- | '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 :: (a -> a -> a) -> [a] -> a
foldl1 f :: a -> a -> a
f (x :: a
x:xs :: [a]
xs)         =  (a -> a -> a) -> a -> [a] -> a
forall a b. (b -> a -> b) -> b -> [a] -> b
foldl a -> a -> a
f a
x [a]
xs
foldl1 _ []             =  String -> a
forall a. String -> a
errorEmptyList "foldl1"

-- | A strict version of 'foldl1'
foldl1'                  :: (a -> a -> a) -> [a] -> a
foldl1' :: (a -> a -> a) -> [a] -> a
foldl1' f :: a -> a -> a
f (x :: a
x:xs :: [a]
xs)         =  (a -> a -> a) -> a -> [a] -> a
forall a b. (b -> a -> b) -> b -> [a] -> b
foldl' a -> a -> a
f a
x [a]
xs
foldl1' _ []             =  String -> a
forall a. String -> a
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 :: [a] -> a
sum                     =  (a -> a -> a) -> a -> [a] -> a
forall a b. (b -> a -> b) -> b -> [a] -> b
foldl a -> a -> a
forall a. Num a => a -> a -> a
(+) 0

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

-- | /O(n)/. '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.

-- This peculiar arrangement is necessary to prevent scanl being rewritten in
-- its own right-hand side.
{-# NOINLINE [1] scanl #-}
scanl                   :: (b -> a -> b) -> b -> [a] -> [b]
scanl :: (b -> a -> b) -> b -> [a] -> [b]
scanl                   = (b -> a -> b) -> b -> [a] -> [b]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanlGo
  where
    scanlGo           :: (b -> a -> b) -> b -> [a] -> [b]
    scanlGo :: (b -> a -> b) -> b -> [a] -> [b]
scanlGo f :: b -> a -> b
f q :: b
q ls :: [a]
ls    = b
q b -> [b] -> [b]
forall t. t -> [t] -> [t]
: (case [a]
ls of
                               []   -> []
                               x :: a
x:xs :: [a]
xs -> (b -> a -> b) -> b -> [a] -> [b]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanlGo b -> a -> b
f (b -> a -> b
f b
q a
x) [a]
xs)

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

{-# INLINE [0] scanlFB #-} -- See Note [Inline FB functions]
scanlFB :: (b -> a -> b) -> (b -> c -> c) -> a -> (b -> c) -> b -> c
scanlFB :: (b -> a -> b) -> (b -> c -> c) -> a -> (b -> c) -> b -> c
scanlFB f :: b -> a -> b
f c :: b -> c -> c
c = \b :: a
b g :: b -> c
g -> (b -> c) -> b -> c
oneShot (\x :: b
x -> let b' :: b
b' = b -> a -> b
f b
x a
b in b
b' b -> c -> c
`c` b -> c
g b
b')
  -- See Note [Left folds via right fold]

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


-- | /O(n)/. 'scanl1' is a variant of 'scanl' that has no starting value
-- argument:
--
-- > scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]

scanl1                  :: (a -> a -> a) -> [a] -> [a]
scanl1 :: (a -> a -> a) -> [a] -> [a]
scanl1 f :: a -> a -> a
f (x :: a
x:xs :: [a]
xs)         =  (a -> a -> a) -> a -> [a] -> [a]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl a -> a -> a
f a
x [a]
xs
scanl1 _ []             =  []

-- | /O(n)/. 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' :: (b -> a -> b) -> b -> [a] -> [b]
scanl' = (b -> a -> b) -> b -> [a] -> [b]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanlGo'
  where
    scanlGo'           :: (b -> a -> b) -> b -> [a] -> [b]
    scanlGo' :: (b -> a -> b) -> b -> [a] -> [b]
scanlGo' f :: b -> a -> b
f !b
q ls :: [a]
ls    = b
q b -> [b] -> [b]
forall t. t -> [t] -> [t]
: (case [a]
ls of
                            []   -> []
                            x :: a
x:xs :: [a]
xs -> (b -> a -> b) -> b -> [a] -> [b]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanlGo' b -> a -> b
f (b -> a -> b
f b
q a
x) [a]
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) (flipSeqScanl' n) bs a)
"scanlList'" [1] forall f a bs .
    foldr (scanlFB' f (:)) (flipSeqScanl' []) bs a = tail (scanl' f a bs)
 #-}

{-# INLINE [0] scanlFB' #-} -- See Note [Inline FB functions]
scanlFB' :: (b -> a -> b) -> (b -> c -> c) -> a -> (b -> c) -> b -> c
scanlFB' :: (b -> a -> b) -> (b -> c -> c) -> a -> (b -> c) -> b -> c
scanlFB' f :: b -> a -> b
f c :: b -> c -> c
c = \b :: a
b g :: b -> c
g -> (b -> c) -> b -> c
oneShot (\x :: b
x -> let !b' :: b
b' = b -> a -> b
f b
x a
b in b
b' b -> c -> c
`c` b -> c
g b
b')
  -- See Note [Left folds via right fold]

{-# INLINE [0] flipSeqScanl' #-}
flipSeqScanl' :: a -> b -> a
flipSeqScanl' :: a -> b -> a
flipSeqScanl' a :: a
a !b
_b = a
a

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

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

-- | 'foldr1' is a variant of 'foldr' that has no starting value argument,
-- and thus must be applied to non-empty lists.

foldr1                  :: (a -> a -> a) -> [a] -> a
foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 f :: a -> a -> a
f = [a] -> a
go
  where go :: [a] -> a
go [x :: a
x]            =  a
x
        go (x :: a
x:xs :: [a]
xs)         =  a -> a -> a
f a
x ([a] -> a
go [a]
xs)
        go []             =  String -> a
forall a. String -> a
errorEmptyList "foldr1"
{-# INLINE [0] foldr1 #-}

-- | /O(n)/. 'scanr' is the right-to-left dual of 'scanl'.
-- Note that
--
-- > head (scanr f z xs) == foldr f z xs.
{-# NOINLINE [1] scanr #-}
scanr                   :: (a -> b -> b) -> b -> [a] -> [b]
scanr :: (a -> b -> b) -> b -> [a] -> [b]
scanr _ q0 :: b
q0 []           =  [b
q0]
scanr f :: a -> b -> b
f q0 :: b
q0 (x :: a
x:xs :: [a]
xs)       =  a -> b -> b
f a
x b
q b -> [b] -> [b]
forall t. t -> [t] -> [t]
: [b]
qs
                           where qs :: [b]
qs@(q :: b
q:_) = (a -> b -> b) -> b -> [a] -> [b]
forall a b. (a -> b -> b) -> b -> [a] -> [b]
scanr a -> b -> b
f b
q0 [a]
xs

-- | /O(n)/. 'scanr1' is a variant of 'scanr' that has no starting
-- value argument.
scanr1                  :: (a -> a -> a) -> [a] -> [a]
scanr1 :: (a -> a -> a) -> [a] -> [a]
scanr1 _ []             =  []
scanr1 _ [x :: a
x]            =  [a
x]
scanr1 f :: a -> a -> a
f (x :: a
x:xs :: [a]
xs)         =  a -> a -> a
f a
x a
q a -> [a] -> [a]
forall t. t -> [t] -> [t]
: [a]
qs
                           where qs :: [a]
qs@(q :: a
q:_) = (a -> a -> a) -> [a] -> [a]
forall a. (a -> a -> a) -> [a] -> [a]
scanr1 a -> a -> a
f [a]
xs

-- | '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
{-# INLINABLE maximum #-}
maximum :: [a] -> a
maximum []              =  String -> a
forall a. String -> a
errorEmptyList "maximum"
maximum xs :: [a]
xs              =  (a -> a -> a) -> [a] -> a
forall a. (a -> a -> a) -> [a] -> a
foldl1 a -> a -> a
forall a. Ord a => a -> a -> a
max [a]
xs

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

-- | '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
{-# INLINABLE minimum #-}
minimum :: [a] -> a
minimum []              =  String -> a
forall a. String -> a
errorEmptyList "minimum"
minimum xs :: [a]
xs              =  (a -> a -> a) -> [a] -> a
forall a. (a -> a -> a) -> [a] -> a
foldl1 a -> a -> a
forall a. Ord a => a -> a -> a
min [a]
xs

{-# SPECIALIZE  minimum :: [Int] -> Int #-}
{-# SPECIALIZE  minimum :: [Integer] -> Integer #-}


-- | 'iterate' @f x@ returns an infinite list of repeated applications
-- of @f@ to @x@:
--
-- > iterate f x == [x, f x, f (f x), ...]
--
-- Note that 'iterate' is lazy, potentially leading to thunk build-up if
-- the consumer doesn't force each iterate. See 'iterate'' for a strict
-- variant of this function.
{-# NOINLINE [1] iterate #-}
iterate :: (a -> a) -> a -> [a]
iterate :: (a -> a) -> a -> [a]
iterate f :: a -> a
f x :: a
x =  a
x a -> [a] -> [a]
forall t. t -> [t] -> [t]
: (a -> a) -> a -> [a]
forall a. (a -> a) -> a -> [a]
iterate a -> a
f (a -> a
f a
x)

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

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


-- | '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' :: (a -> a) -> a -> [a]
iterate' f :: a -> a
f x :: a
x =
    let x' :: a
x' = a -> a
f a
x
    in a
x' a -> [a] -> [a]
forall a b. a -> b -> b
`seq` (a
x a -> [a] -> [a]
forall t. t -> [t] -> [t]
: (a -> a) -> a -> [a]
forall a. (a -> a) -> a -> [a]
iterate' a -> a
f a
x')

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

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


-- | 'repeat' @x@ is an infinite list, with @x@ the value of every element.
repeat :: a -> [a]
{-# INLINE [0] repeat #-}
-- The pragma just gives the rules more chance to fire
repeat :: a -> [a]
repeat x :: a
x = [a]
xs where xs :: [a]
xs = a
x a -> [a] -> [a]
forall t. t -> [t] -> [t]
: [a]
xs

{-# INLINE [0] repeatFB #-}     -- ditto -- See Note [Inline FB functions]
repeatFB :: (a -> b -> b) -> a -> b
repeatFB :: (a -> b -> b) -> a -> b
repeatFB c :: a -> b -> b
c x :: a
x = b
xs where xs :: b
xs = a
x a -> b -> b
`c` b
xs


{-# RULES
"repeat"    [~1] forall x. repeat x = build (\c _n -> repeatFB c x)
"repeatFB"  [1]  repeatFB (:)       = repeat
 #-}

-- | '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.
{-# INLINE replicate #-}
replicate               :: Int -> a -> [a]
replicate :: Int -> a -> [a]
replicate n :: Int
n x :: a
x           =  Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
take Int
n (a -> [a]
forall a. a -> [a]
repeat a
x)

-- | 'cycle' ties a finite list into a circular one, or equivalently,
-- the infinite repetition of the original list.  It is the identity
-- on infinite lists.

cycle                   :: [a] -> [a]
cycle :: [a] -> [a]
cycle []                = String -> [a]
forall a. String -> a
errorEmptyList "cycle"
cycle xs :: [a]
xs                = [a]
xs' where xs' :: [a]
xs' = [a]
xs [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
xs'

-- | 'takeWhile', applied to a predicate @p@ and a list @xs@, returns the
-- 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] == []
--

{-# NOINLINE [1] takeWhile #-}
takeWhile               :: (a -> Bool) -> [a] -> [a]
takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile _ []          =  []
takeWhile p :: a -> Bool
p (x :: a
x:xs :: [a]
xs)
            | a -> Bool
p a
x       =  a
x a -> [a] -> [a]
forall t. t -> [t] -> [t]
: (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile a -> Bool
p [a]
xs
            | Bool
otherwise =  []

{-# INLINE [0] takeWhileFB #-} -- See Note [Inline FB functions]
takeWhileFB :: (a -> Bool) -> (a -> b -> b) -> b -> a -> b -> b
takeWhileFB :: (a -> Bool) -> (a -> b -> b) -> b -> a -> b -> b
takeWhileFB p :: a -> Bool
p c :: a -> b -> b
c n :: b
n = \x :: a
x r :: b
r -> if a -> Bool
p a
x then a
x a -> b -> b
`c` b
r else b
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
 #-}

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

dropWhile               :: (a -> Bool) -> [a] -> [a]
dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile _ []          =  []
dropWhile p :: a -> Bool
p xs :: [a]
xs@(x :: a
x:xs' :: [a]
xs')
            | a -> Bool
p a
x       =  (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
dropWhile a -> Bool
p [a]
xs'
            | Bool
otherwise =  [a]
xs

-- | 'take' @n@, applied to a list @xs@, returns the prefix of @xs@
-- 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] == []
--
-- It is an instance of the more general 'Data.List.genericTake',
-- in which @n@ may be of any integral type.
take                   :: Int -> [a] -> [a]
#if defined(USE_REPORT_PRELUDE)
take n _      | n <= 0 =  []
take _ []              =  []
take n (x:xs)          =  x : take (n-1) xs
#else

{- 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 #-}
take :: Int -> [a] -> [a]
take n :: Int
n xs :: [a]
xs | 0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n     = Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
unsafeTake Int
n [a]
xs
          | Bool
otherwise = []

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

{-# RULES
"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)
"unsafeTakeList"  [1] forall n xs . foldr (takeFB (:) []) (flipSeqTake []) xs n
                                        = unsafeTake n xs
 #-}

{-# 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
-- bad for strictness analysis and unboxing, and leads to increased
-- allocation in T7257.
flipSeqTake :: a -> Int -> a
flipSeqTake :: a -> Int -> a
flipSeqTake x :: a
x !Int
_n = a
x

{-# INLINE [0] takeFB #-} -- See Note [Inline FB functions]
takeFB :: (a -> b -> b) -> b -> a -> (Int -> b) -> Int -> b
-- 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 :: (a -> b -> b) -> b -> a -> (Int -> b) -> Int -> b
takeFB c :: a -> b -> b
c n :: b
n x :: a
x xs :: Int -> b
xs
  = \ m :: Int
m -> case Int
m of
            1 -> a
x a -> b -> b
`c` b
n
            _ -> a
x a -> b -> b
`c` Int -> b
xs (Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- 1)
#endif

-- | '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]
#if defined(USE_REPORT_PRELUDE)
drop n xs     | n <= 0 =  xs
drop _ []              =  []
drop n (_:xs)          =  drop (n-1) xs
#else /* hack away */
{-# INLINE drop #-}
drop :: Int -> [a] -> [a]
drop n :: Int
n ls :: [a]
ls
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= 0     = [a]
ls
  | Bool
otherwise  = Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
unsafeDrop Int
n [a]
ls
  where
    -- A version of drop that drops the whole list if given an argument
    -- less than 1
    unsafeDrop :: Int -> [a] -> [a]
    unsafeDrop :: Int -> [a] -> [a]
unsafeDrop !Int
_ []     = []
    unsafeDrop 1  (_:xs :: [a]
xs) = [a]
xs
    unsafeDrop m :: Int
m  (_:xs :: [a]
xs) = Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
unsafeDrop (Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- 1) [a]
xs
#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])

#if defined(USE_REPORT_PRELUDE)
splitAt n xs           =  (take n xs, drop n xs)
#else
splitAt :: Int -> [a] -> ([a], [a])
splitAt n :: Int
n ls :: [a]
ls
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= 0 = ([], [a]
ls)
  | Bool
otherwise          = Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
splitAt' Int
n [a]
ls
    where
        splitAt' :: Int -> [a] -> ([a], [a])
        splitAt' :: Int -> [a] -> ([a], [a])
splitAt' _  []     = ([], [])
        splitAt' 1  (x :: a
x:xs :: [a]
xs) = ([a
x], [a]
xs)
        splitAt' m :: Int
m  (x :: a
x:xs :: [a]
xs) = (a
xa -> [a] -> [a]
forall t. t -> [t] -> [t]
:[a]
xs', [a]
xs'')
          where
            (xs' :: [a]
xs', xs'' :: [a]
xs'') = Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
splitAt' (Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- 1) [a]
xs
#endif /* USE_REPORT_PRELUDE */

-- | '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:
--
-- > 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])
--
-- 'span' @p xs@ is equivalent to @('takeWhile' p xs, 'dropWhile' p xs)@

span                    :: (a -> Bool) -> [a] -> ([a],[a])
span :: (a -> Bool) -> [a] -> ([a], [a])
span _ xs :: [a]
xs@[]            =  ([a]
xs, [a]
xs)
span p :: a -> Bool
p xs :: [a]
xs@(x :: a
x:xs' :: [a]
xs')
         | a -> Bool
p a
x          =  let (ys :: [a]
ys,zs :: [a]
zs) = (a -> Bool) -> [a] -> ([a], [a])
forall a. (a -> Bool) -> [a] -> ([a], [a])
span a -> Bool
p [a]
xs' in (a
xa -> [a] -> [a]
forall t. t -> [t] -> [t]
:[a]
ys,[a]
zs)
         | Bool
otherwise    =  ([],[a]
xs)

-- | '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:
--
-- > 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)@.

break                   :: (a -> Bool) -> [a] -> ([a],[a])
#if defined(USE_REPORT_PRELUDE)
break p                 =  span (not . p)
#else
-- HBC version (stolen)
break :: (a -> Bool) -> [a] -> ([a], [a])
break _ xs :: [a]
xs@[]           =  ([a]
xs, [a]
xs)
break p :: a -> Bool
p xs :: [a]
xs@(x :: a
x:xs' :: [a]
xs')
           | a -> Bool
p a
x        =  ([],[a]
xs)
           | Bool
otherwise  =  let (ys :: [a]
ys,zs :: [a]
zs) = (a -> Bool) -> [a] -> ([a], [a])
forall a. (a -> Bool) -> [a] -> ([a], [a])
break a -> Bool
p [a]
xs' in (a
xa -> [a] -> [a]
forall t. t -> [t] -> [t]
:[a]
ys,[a]
zs)
#endif

-- | 'reverse' @xs@ returns the elements of @xs@ in reverse order.
-- @xs@ must be finite.
reverse                 :: [a] -> [a]
#if defined(USE_REPORT_PRELUDE)
reverse                 =  foldl (flip (:)) []
#else
reverse :: [a] -> [a]
reverse l :: [a]
l =  [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
rev [a]
l []
  where
    rev :: [a] -> [a] -> [a]
rev []     a :: [a]
a = [a]
a
    rev (x :: a
x:xs :: [a]
xs) a :: [a]
a = [a] -> [a] -> [a]
rev [a]
xs (a
xa -> [a] -> [a]
forall t. t -> [t] -> [t]
:[a]
a)
#endif

-- | '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
#if defined(USE_REPORT_PRELUDE)
and                     =  foldr (&&) True
#else
and :: [Bool] -> Bool
and []          =  Bool
True
and (x :: Bool
x:xs :: [Bool]
xs)      =  Bool
x Bool -> Bool -> Bool
&& [Bool] -> Bool
and [Bool]
xs
{-# NOINLINE [1] and #-}

{-# RULES
"and/build"     forall (g::forall b.(Bool->b->b)->b->b) .
                and (build g) = g (&&) True
 #-}
#endif

-- | '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
#if defined(USE_REPORT_PRELUDE)
or                      =  foldr (||) False
#else
or :: [Bool] -> Bool
or []           =  Bool
False
or (x :: Bool
x:xs :: [Bool]
xs)       =  Bool
x Bool -> Bool -> Bool
|| [Bool] -> Bool
or [Bool]
xs
{-# NOINLINE [1] or #-}

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

-- | Applied to a predicate and a list, 'any' determines if any element
-- 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.
any                     :: (a -> Bool) -> [a] -> Bool

#if defined(USE_REPORT_PRELUDE)
any p                   =  or . map p
#else
any :: (a -> Bool) -> [a] -> Bool
any _ []        = Bool
False
any p :: a -> Bool
p (x :: a
x:xs :: [a]
xs)    = a -> Bool
p a
x Bool -> Bool -> Bool
|| (a -> Bool) -> [a] -> Bool
forall a. (a -> Bool) -> [a] -> Bool
any a -> Bool
p [a]
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

-- | Applied to a predicate and a list, 'all' determines if all elements
-- 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.
all                     :: (a -> Bool) -> [a] -> Bool
#if defined(USE_REPORT_PRELUDE)
all p                   =  and . map p
#else
all :: (a -> Bool) -> [a] -> Bool
all _ []        =  Bool
True
all p :: a -> Bool
p (x :: a
x:xs :: [a]
xs)    =  a -> Bool
p a
x Bool -> Bool -> Bool
&& (a -> Bool) -> [a] -> Bool
forall a. (a -> Bool) -> [a] -> Bool
all a -> Bool
p [a]
xs

{-# NOINLINE [1] all #-}

{-# RULES
"all/build"     forall p (g::forall b.(a->b->b)->b->b) .
                all p (build g) = g ((&&) . p) True
 #-}
#endif

-- | 'elem' is the list membership predicate, usually written in infix form,
-- e.g., @x \`elem\` xs@.  For the result to be
-- '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.
elem                    :: (Eq a) => a -> [a] -> Bool
#if defined(USE_REPORT_PRELUDE)
elem x                  =  any (== x)
#else
elem :: a -> [a] -> Bool
elem _ []       = Bool
False
elem x :: a
x (y :: a
y:ys :: [a]
ys)   = a
xa -> a -> Bool
forall a. Eq a => a -> a -> Bool
==a
y Bool -> Bool -> Bool
|| a -> [a] -> Bool
forall a. Eq a => a -> [a] -> Bool
elem a
x [a]
ys
{-# 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

-- | 'notElem' is the negation of 'elem'.
notElem                 :: (Eq a) => a -> [a] -> Bool
#if defined(USE_REPORT_PRELUDE)
notElem x               =  all (/= x)
#else
notElem :: a -> [a] -> Bool
notElem _ []    =  Bool
True
notElem x :: a
x (y :: a
y:ys :: [a]
ys)=  a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
y Bool -> Bool -> Bool
&& a -> [a] -> Bool
forall a. Eq a => a -> [a] -> Bool
notElem a
x [a]
ys
{-# 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
 #-}
#endif

-- | /O(n)/. 'lookup' @key assocs@ looks up a key in an association list.
--
-- >>> lookup 2 [(1, "first"), (2, "second"), (3, "third")]
-- Just "second"
lookup                  :: (Eq a) => a -> [(a,b)] -> Maybe b
lookup :: a -> [(a, b)] -> Maybe b
lookup _key :: a
_key []          =  Maybe b
forall a. Maybe a
Nothing
lookup  key :: a
key ((x :: a
x,y :: b
y):xys :: [(a, b)]
xys)
    | a
key a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
x           =  b -> Maybe b
forall a. a -> Maybe a
Just b
y
    | Bool
otherwise         =  a -> [(a, b)] -> Maybe b
forall a b. Eq a => a -> [(a, b)] -> Maybe b
lookup a
key [(a, b)]
xys

-- | Map a function over a list and concatenate the results.
concatMap               :: (a -> [b]) -> [a] -> [b]
concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f :: a -> [b]
f             =  (a -> [b] -> [b]) -> [b] -> [a] -> [b]
forall a b. (a -> b -> b) -> b -> [a] -> b
foldr ([b] -> [b] -> [b]
forall a. [a] -> [a] -> [a]
(++) ([b] -> [b] -> [b]) -> (a -> [b]) -> a -> [b] -> [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> [b]
f) []

{-# NOINLINE [1] concatMap #-}

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


-- | Concatenate a list of lists.
concat :: [[a]] -> [a]
concat :: [[a]] -> [a]
concat = ([a] -> [a] -> [a]) -> [a] -> [[a]] -> [a]
forall a b. (a -> b -> b) -> b -> [a] -> b
foldr [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
(++) []

{-# NOINLINE [1] concat #-}

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

-- | 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.
(!!)                    :: [a] -> Int -> a
#if defined(USE_REPORT_PRELUDE)
xs     !! n | n < 0 =  errorWithoutStackTrace "Prelude.!!: negative index"
[]     !! _         =  errorWithoutStackTrace "Prelude.!!: index too large"
(x:_)  !! 0         =  x
(_:xs) !! n         =  xs !! (n-1)
#else

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

negIndex :: a
negIndex :: a
negIndex = String -> a
forall a. String -> a
errorWithoutStackTrace (String -> a) -> String -> a
forall a b. (a -> b) -> a -> b
$ String
prel_list_str String -> String -> String
forall a. [a] -> [a] -> [a]
++ "!!: negative index"

{-# INLINABLE (!!) #-}
xs :: [a]
xs !! :: [a] -> Int -> a
!! n :: Int
n
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< 0     = a
forall a. a
negIndex
  | Bool
otherwise = (a -> (Int -> a) -> Int -> a) -> (Int -> a) -> [a] -> Int -> a
forall a b. (a -> b -> b) -> b -> [a] -> b
foldr (\x :: a
x r :: Int -> a
r k :: Int
k -> case Int
k of
                                   0 -> a
x
                                   _ -> Int -> a
r (Int
kInt -> Int -> Int
forall a. Num a => a -> a -> a
-1)) Int -> a
forall a. Int -> a
tooLarge [a]
xs Int
n
#endif

--------------------------------------------------------------
-- The zip family
--------------------------------------------------------------

foldr2 :: (a -> b -> c -> c) -> c -> [a] -> [b] -> c
foldr2 :: (a -> b -> c -> c) -> c -> [a] -> [b] -> c
foldr2 k :: a -> b -> c -> c
k z :: c
z = [a] -> [b] -> c
go
  where
        go :: [a] -> [b] -> c
go []    _ys :: [b]
_ys     = c
z
        go _xs :: [a]
_xs   []      = c
z
        go (x :: a
x:xs :: [a]
xs) (y :: b
y:ys :: [b]
ys) = a -> b -> c -> c
k a
x b
y ([a] -> [b] -> c
go [a]
xs [b]
ys)
{-# INLINE [0] foldr2 #-}

foldr2_left :: (a -> b -> c -> d) -> d -> a -> ([b] -> c) -> [b] -> d
foldr2_left :: (a -> b -> c -> d) -> d -> a -> ([b] -> c) -> [b] -> d
foldr2_left _k :: a -> b -> c -> d
_k  z :: d
z _x :: a
_x _r :: [b] -> c
_r []     = d
z
foldr2_left  k :: a -> b -> c -> d
k _z :: d
_z  x :: a
x  r :: [b] -> c
r (y :: b
y:ys :: [b]
ys) = a -> b -> c -> d
k a
x b
y ([b] -> c
r [b]
ys)

-- foldr2 k z xs ys = foldr (foldr2_left k z)  (\_ -> z) xs ys
{-# RULES
"foldr2/left"   forall k z ys (g::forall b.(a->b->b)->b->b) .
                  foldr2 k z (build g) ys = g (foldr2_left  k z) (\_ -> z) ys
 #-}

foldr3 :: (a -> b -> c -> d -> d) -> d -> [a] -> [b] -> [c] -> d
foldr3 :: (a -> b -> c -> d -> d) -> d -> [a] -> [b] -> [c] -> d
foldr3 k :: a -> b -> c -> d -> d
k z :: d
z = [a] -> [b] -> [c] -> d
go
  where
    go :: [a] -> [b] -> [c] -> d
go  []    _      _      = d
z
    go  _     []     _      = d
z
    go  _     _      []     = d
z
    go (a :: a
a:as :: [a]
as) (b :: b
b:bs :: [b]
bs) (c :: c
c:cs :: [c]
cs) = a -> b -> c -> d -> d
k a
a b
b c
c ([a] -> [b] -> [c] -> d
go [a]
as [b]
bs [c]
cs)
{-# INLINE [0] foldr3 #-}


foldr3_left :: (a -> b -> c -> d -> e) -> e -> a ->
               ([b] -> [c] -> d) -> [b] -> [c] -> e
foldr3_left :: (a -> b -> c -> d -> e)
-> e -> a -> ([b] -> [c] -> d) -> [b] -> [c] -> e
foldr3_left k :: a -> b -> c -> d -> e
k _z :: e
_z a :: a
a r :: [b] -> [c] -> d
r (b :: b
b:bs :: [b]
bs) (c :: c
c:cs :: [c]
cs) = a -> b -> c -> d -> e
k a
a b
b c
c ([b] -> [c] -> d
r [b]
bs [c]
cs)
foldr3_left _  z :: e
z _ _  _      _     = e
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)
 #-}

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

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

----------------------------------------------
-- | /O(min(m,n))/. 'zip' takes two lists and returns a list of corresponding
-- pairs.
--
-- > zip [1, 2] ['a', 'b'] = [(1, 'a'), (2, 'b')]
--
-- If one input list is short, excess elements of the longer list are
-- discarded:
--
-- > zip [1] ['a', 'b'] = [(1, 'a')]
-- > zip [1, 2] ['a'] = [(1, 'a')]
--
-- 'zip' is right-lazy:
--
-- > zip [] _|_ = []
-- > zip _|_ [] = _|_
--
-- 'zip' is capable of list fusion, but it is restricted to its
-- first list argument and its resulting list.
{-# NOINLINE [1] zip #-}
zip :: [a] -> [b] -> [(a,b)]
zip :: [a] -> [b] -> [(a, b)]
zip []     _bs :: [b]
_bs    = []
zip _as :: [a]
_as    []     = []
zip (a :: a
a:as :: [a]
as) (b :: b
b:bs :: [b]
bs) = (a
a,b
b) (a, b) -> [(a, b)] -> [(a, b)]
forall t. t -> [t] -> [t]
: [a] -> [b] -> [(a, b)]
forall a b. [a] -> [b] -> [(a, b)]
zip [a]
as [b]
bs

{-# INLINE [0] zipFB #-} -- See Note [Inline FB functions]
zipFB :: ((a, b) -> c -> d) -> a -> b -> c -> d
zipFB :: ((a, b) -> c -> d) -> a -> b -> c -> d
zipFB c :: (a, b) -> c -> d
c = \x :: a
x y :: b
y r :: c
r -> (a
x,b
y) (a, b) -> c -> d
`c` c
r

{-# RULES
"zip"      [~1] forall xs ys. zip xs ys = build (\c n -> foldr2 (zipFB c) n xs ys)
"zipList"  [1]  foldr2 (zipFB (:)) []   = zip
 #-}

----------------------------------------------
-- | 'zip3' takes three lists and returns a list of triples, analogous to
-- 'zip'.
-- It is capable of list fusion, but it is restricted to its
-- first list argument and its resulting list.
{-# NOINLINE [1] zip3 #-}
zip3 :: [a] -> [b] -> [c] -> [(a,b,c)]
-- Specification
-- zip3 =  zipWith3 (,,)
zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
zip3 (a :: a
a:as :: [a]
as) (b :: b
b:bs :: [b]
bs) (c :: c
c:cs :: [c]
cs) = (a
a,b
b,c
c) (a, b, c) -> [(a, b, c)] -> [(a, b, c)]
forall t. t -> [t] -> [t]
: [a] -> [b] -> [c] -> [(a, b, c)]
forall a b c. [a] -> [b] -> [c] -> [(a, b, c)]
zip3 [a]
as [b]
bs [c]
cs
zip3 _      _      _      = []

{-# INLINE [0] zip3FB #-} -- See Note [Inline FB functions]
zip3FB :: ((a,b,c) -> xs -> xs') -> a -> b -> c -> xs -> xs'
zip3FB :: ((a, b, c) -> xs -> xs') -> a -> b -> c -> xs -> xs'
zip3FB cons :: (a, b, c) -> xs -> xs'
cons = \a :: a
a b :: b
b c :: c
c r :: xs
r -> (a
a,b
b,c
c) (a, b, c) -> xs -> xs'
`cons` xs
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
 #-}

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

----------------------------------------------
-- | /O(min(m,n))/. '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:
--
-- >>> zipWith (+) [1, 2, 3] [4, 5, 6]
-- [5,7,9]
--
-- 'zipWith' is right-lazy:
--
-- > zipWith f [] _|_ = []
--
-- 'zipWith' is capable of list fusion, but it is restricted to its
-- first list argument and its resulting list.
{-# NOINLINE [1] zipWith #-}
zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f :: a -> b -> c
f = [a] -> [b] -> [c]
go
  where
    go :: [a] -> [b] -> [c]
go [] _ = []
    go _ [] = []
    go (x :: a
x:xs :: [a]
xs) (y :: b
y:ys :: [b]
ys) = a -> b -> c
f a
x b
y c -> [c] -> [c]
forall t. t -> [t] -> [t]
: [a] -> [b] -> [c]
go [a]
xs [b]
ys

-- zipWithFB must have arity 2 since it gets two arguments in the "zipWith"
-- rule; it might not get inlined otherwise
{-# INLINE [0] zipWithFB #-} -- See Note [Inline FB functions]
zipWithFB :: (a -> b -> c) -> (d -> e -> a) -> d -> e -> b -> c
zipWithFB :: (a -> b -> c) -> (d -> e -> a) -> d -> e -> b -> c
zipWithFB c :: a -> b -> c
c f :: d -> e -> a
f = \x :: d
x y :: e
y r :: b
r -> (d
x d -> e -> a
`f` e
y) a -> b -> c
`c` b
r

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

-- | 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'.
-- It is capable of list fusion, but it is restricted to its
-- first list argument and its resulting list.
{-# NOINLINE [1] zipWith3 #-}
zipWith3                :: (a->b->c->d) -> [a]->[b]->[c]->[d]
zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
zipWith3 z :: a -> b -> c -> d
z = [a] -> [b] -> [c] -> [d]
go
  where
    go :: [a] -> [b] -> [c] -> [d]
go (a :: a
a:as :: [a]
as) (b :: b
b:bs :: [b]
bs) (c :: c
c:cs :: [c]
cs) = a -> b -> c -> d
z a
a b
b c
c d -> [d] -> [d]
forall t. t -> [t] -> [t]
: [a] -> [b] -> [c] -> [d]
go [a]
as [b]
bs [c]
cs
    go _ _ _                = []

{-# INLINE [0] zipWith3FB #-} -- See Note [Inline FB functions]
zipWith3FB :: (d -> xs -> xs') -> (a -> b -> c -> d) -> a -> b -> c -> xs -> xs'
zipWith3FB :: (d -> xs -> xs') -> (a -> b -> c -> d) -> a -> b -> c -> xs -> xs'
zipWith3FB cons :: d -> xs -> xs'
cons func :: a -> b -> c -> d
func = \a :: a
a b :: b
b c :: c
c r :: xs
r -> (a -> b -> c -> d
func a
a b
b c
c) d -> xs -> xs'
`cons` xs
r

{-# RULES
"zipWith3"      [~1] forall f as bs cs.   zipWith3 f as bs cs = build (\c n -> foldr3 (zipWith3FB c f) n as bs cs)
"zipWith3List"  [1]  forall f.   foldr3 (zipWith3FB (:) f) [] = zipWith3 f
 #-}

-- | 'unzip' transforms a list of pairs into a list of first components
-- and a list of second components.
unzip    :: [(a,b)] -> ([a],[b])
{-# INLINE unzip #-}
unzip :: [(a, b)] -> ([a], [b])
unzip    =  ((a, b) -> ([a], [b]) -> ([a], [b]))
-> ([a], [b]) -> [(a, b)] -> ([a], [b])
forall a b. (a -> b -> b) -> b -> [a] -> b
foldr (\(a :: a
a,b :: b
b) ~(as :: [a]
as,bs :: [b]
bs) -> (a
aa -> [a] -> [a]
forall t. t -> [t] -> [t]
:[a]
as,b
bb -> [b] -> [b]
forall t. t -> [t] -> [t]
:[b]
bs)) ([],[])

-- | The 'unzip3' function takes a list of triples and returns three
-- lists, analogous to 'unzip'.
unzip3   :: [(a,b,c)] -> ([a],[b],[c])
{-# INLINE unzip3 #-}
unzip3 :: [(a, b, c)] -> ([a], [b], [c])
unzip3   =  ((a, b, c) -> ([a], [b], [c]) -> ([a], [b], [c]))
-> ([a], [b], [c]) -> [(a, b, c)] -> ([a], [b], [c])
forall a b. (a -> b -> b) -> b -> [a] -> b
foldr (\(a :: a
a,b :: b
b,c :: c
c) ~(as :: [a]
as,bs :: [b]
bs,cs :: [c]
cs) -> (a
aa -> [a] -> [a]
forall t. t -> [t] -> [t]
:[a]
as,b
bb -> [b] -> [b]
forall t. t -> [t] -> [t]
:[b]
bs,c
cc -> [c] -> [c]
forall t. t -> [t] -> [t]
:[c]
cs))
                  ([],[],[])

--------------------------------------------------------------
-- Error code
--------------------------------------------------------------

-- Common up near identical calls to `error' to reduce the number
-- constant strings created when compiled:

errorEmptyList :: String -> a
errorEmptyList :: String -> a
errorEmptyList fun :: String
fun =
  String -> a
forall a. String -> a
errorWithoutStackTrace (String
prel_list_str String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
fun String -> String -> String
forall a. [a] -> [a] -> [a]
++ ": empty list")

prel_list_str :: String
prel_list_str :: String
prel_list_str = "Prelude."