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

Safe Haskell | Trustworthy |

Language | Haskell2010 |

The List data type and its operations

## Synopsis

- data List a
- foldr :: (a -> b -> b) -> b -> [a] -> b
- foldr' :: (a -> b -> b) -> b -> [a] -> b
- foldr1 :: HasCallStack => (a -> a -> a) -> [a] -> a
- foldl :: forall a b. (b -> a -> b) -> b -> [a] -> b
- foldl' :: forall a b. (b -> a -> b) -> b -> [a] -> b
- foldl1 :: HasCallStack => (a -> a -> a) -> [a] -> a
- null :: [a] -> Bool
- length :: [a] -> Int
- elem :: Eq a => a -> [a] -> Bool
- notElem :: Eq a => a -> [a] -> Bool
- maximum :: (Ord a, HasCallStack) => [a] -> a
- minimum :: (Ord a, HasCallStack) => [a] -> a
- sum :: Num a => [a] -> a
- product :: Num a => [a] -> a
- and :: [Bool] -> Bool
- or :: [Bool] -> Bool
- any :: (a -> Bool) -> [a] -> Bool
- all :: (a -> Bool) -> [a] -> Bool
- foldl1' :: HasCallStack => (a -> a -> a) -> [a] -> a
- concat :: [[a]] -> [a]
- concatMap :: (a -> [b]) -> [a] -> [b]
- map :: (a -> b) -> [a] -> [b]
- (++) :: [a] -> [a] -> [a]
- filter :: (a -> Bool) -> [a] -> [a]
- lookup :: Eq a => a -> [(a, b)] -> Maybe b
- head :: HasCallStack => [a] -> a
- last :: HasCallStack => [a] -> a
- tail :: HasCallStack => [a] -> [a]
- init :: HasCallStack => [a] -> [a]
- uncons :: [a] -> Maybe (a, [a])
- unsnoc :: [a] -> Maybe ([a], a)
- (!?) :: [a] -> Int -> Maybe a
- (!!) :: HasCallStack => [a] -> Int -> a
- scanl :: (b -> a -> b) -> b -> [a] -> [b]
- scanl1 :: (a -> a -> a) -> [a] -> [a]
- scanl' :: (b -> a -> b) -> b -> [a] -> [b]
- scanr :: (a -> b -> b) -> b -> [a] -> [b]
- scanr1 :: (a -> a -> a) -> [a] -> [a]
- iterate :: (a -> a) -> a -> [a]
- iterate' :: (a -> a) -> a -> [a]
- repeat :: a -> [a]
- replicate :: Int -> a -> [a]
- cycle :: HasCallStack => [a] -> [a]
- take :: Int -> [a] -> [a]
- drop :: Int -> [a] -> [a]
- splitAt :: Int -> [a] -> ([a], [a])
- takeWhile :: (a -> Bool) -> [a] -> [a]
- dropWhile :: (a -> Bool) -> [a] -> [a]
- span :: (a -> Bool) -> [a] -> ([a], [a])
- break :: (a -> Bool) -> [a] -> ([a], [a])
- reverse :: [a] -> [a]
- zip :: [a] -> [b] -> [(a, b)]
- zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
- zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
- unzip :: [(a, b)] -> ([a], [b])
- unzip3 :: [(a, b, c)] -> ([a], [b], [c])
- errorEmptyList :: HasCallStack => String -> a
- augment :: (forall b. (a -> b -> b) -> b -> b) -> [a] -> [a]
- build :: (forall b. (a -> b -> b) -> b -> b) -> [a]

# Documentation

The builtin list type, usually written in its non-prefix form `[a]`

.

#### Examples

Unless the OverloadedLists extension is enabled, list literals are
syntactic sugar for repeated applications of `:`

and `[]`

.

`>>>`

True`1:2:3:4:[] == [1,2,3,4]`

Similarly, unless the OverloadedStrings extension is enabled, string literals are syntactic sugar for a lists of characters.

`>>>`

True`['h','e','l','l','o'] == "hello"`

*Since: ghc-prim-0.10.0*

#### Instances

MonadFail [] Source # |
| ||||

Defined in Control.Monad.Fail | |||||

MonadFix [] Source # |
| ||||

Defined in Control.Monad.Fix | |||||

MonadZip [] Source # |
| ||||

Foldable [] Source # |
| ||||

Defined in Data.Foldable fold :: Monoid m => [m] -> m Source # foldMap :: Monoid m => (a -> m) -> [a] -> m Source # foldMap' :: Monoid m => (a -> m) -> [a] -> m Source # foldr :: (a -> b -> b) -> b -> [a] -> b Source # foldr' :: (a -> b -> b) -> b -> [a] -> b Source # foldl :: (b -> a -> b) -> b -> [a] -> b Source # foldl' :: (b -> a -> b) -> b -> [a] -> b Source # foldr1 :: (a -> a -> a) -> [a] -> a Source # foldl1 :: (a -> a -> a) -> [a] -> a Source # elem :: Eq a => a -> [a] -> Bool Source # maximum :: Ord a => [a] -> a Source # minimum :: Ord a => [a] -> a Source # | |||||

Eq1 [] Source # |
| ||||

Ord1 [] Source # |
| ||||

Defined in Data.Functor.Classes liftCompare :: (a -> b -> Ordering) -> [a] -> [b] -> Ordering Source # | |||||

Read1 [] Source # |
| ||||

Defined in Data.Functor.Classes | |||||

Show1 [] Source # |
| ||||

Traversable [] Source # |
| ||||

Alternative [] Source # | Combines lists by concatenation, starting from the empty list.
| ||||

Applicative [] Source # |
| ||||

Functor [] Source # |
| ||||

Monad [] Source # |
| ||||

MonadPlus [] Source # | Combines lists by concatenation, starting from the empty list.
| ||||

Generic1 [] Source # | |||||

Defined in GHC.Generics
| |||||

Data a => Data [a] Source # | For historical reasons, the constructor name used for
| ||||

Defined in Data.Data gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> [a] -> c [a] Source # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c [a] Source # toConstr :: [a] -> Constr Source # dataTypeOf :: [a] -> DataType Source # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c [a]) Source # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c [a]) Source # gmapT :: (forall b. Data b => b -> b) -> [a] -> [a] Source # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> [a] -> r Source # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> [a] -> r Source # gmapQ :: (forall d. Data d => d -> u) -> [a] -> [u] Source # gmapQi :: Int -> (forall d. Data d => d -> u) -> [a] -> u Source # gmapM :: Monad m => (forall d. Data d => d -> m d) -> [a] -> m [a] Source # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> [a] -> m [a] Source # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> [a] -> m [a] Source # | |||||

a ~ Char => IsString [a] Source # |
| ||||

Defined in Data.String fromString :: String -> [a] Source # | |||||

Monoid [a] Source # |
| ||||

Semigroup [a] Source # |
| ||||

Generic [a] Source # | |||||

Defined in GHC.Generics
| |||||

IsList [a] Source # |
| ||||

Read a => Read [a] Source # |
| ||||

Show a => Show [a] Source # |
| ||||

IsChar c => PrintfArg [c] Source # |
| ||||

Defined in Text.Printf formatArg :: [c] -> FieldFormatter Source # parseFormat :: [c] -> ModifierParser Source # | |||||

IsChar c => PrintfType [c] Source # |
| ||||

Defined in Text.Printf | |||||

Eq a => Eq [a] | |||||

Ord a => Ord [a] | |||||

type Rep1 [] Source # |
| ||||

Defined in GHC.Generics type Rep1 [] = D1 ('MetaData "List" "GHC.Types" "ghc-prim" 'False) (C1 ('MetaCons "[]" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons ":" ('InfixI 'RightAssociative 5) 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1 :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec1 []))) | |||||

type Rep [a] Source # |
| ||||

Defined in GHC.Generics type Rep [a] = D1 ('MetaData "List" "GHC.Types" "ghc-prim" 'False) (C1 ('MetaCons "[]" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons ":" ('InfixI 'RightAssociative 5) 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [a]))) | |||||

type Item [a] Source # | |||||

Defined in GHC.IsList type Item [a] = a |

foldr :: (a -> b -> b) -> b -> [a] -> b Source #

`foldr`

, applied to a binary operator, a starting value (typically
the right-identity of the operator), and a list, reduces the list
using the binary operator, from right to left:

foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

foldr' :: (a -> b -> b) -> b -> [a] -> b Source #

`foldr'`

is a variant of `foldr`

that begins list reduction from the last
element and evaluates the accumulator strictly as it unwinds the stack back
to the beginning of the list. The input list *must* be finite, otherwise
`foldr'`

runs out of space (*diverges*).

Note that if the function that combines the accumulated value with each
element is strict in the accumulator, other than a possible improvement
in the constant factor, you get the same \(\mathcal{O}(n)\) space cost
as with just `foldr`

.

If you want a strict right fold in constant space, you need a structure
that supports faster than \(\mathcal{O}(n)\) access to the right-most
element, such as `Seq`

from the `containers`

package.

Use of this function is a hint that the `[]`

structure may be a poor fit
for the task at hand. If the order in which the elements are combined is
not important, use `foldl'`

instead.

`>>>`

10`foldr' (+) [1..4] -- Use foldl' instead!`

`>>>`

False`foldr' (&&) [True, False, True, True] -- Use foldr instead!`

`>>>`

True`foldr' (||) [False, False, True, True] -- Use foldr instead!`

foldr1 :: HasCallStack => (a -> a -> a) -> [a] -> a Source #

`foldr1`

is a variant of `foldr`

that has no starting value argument,
and thus must be applied to non-empty lists. Note that unlike `foldr`

, the accumulated value must be of the same type as the list elements.

`>>>`

10`foldr1 (+) [1..4]`

`>>>`

*** Exception: Prelude.foldr1: empty list`foldr1 (+) []`

`>>>`

-2`foldr1 (-) [1..4]`

`>>>`

False`foldr1 (&&) [True, False, True, True]`

`>>>`

True`foldr1 (||) [False, False, True, True]`

`>>>`

*** Exception: stack overflow`force $ foldr1 (+) [1..]`

foldl :: forall a b. (b -> a -> b) -> b -> [a] -> b Source #

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

`>>>`

10`foldl (+) 0 [1..4]`

`>>>`

42`foldl (+) 42 []`

`>>>`

90`foldl (-) 100 [1..4]`

`>>>`

"dcbafoo"`foldl (\reversedString nextChar -> nextChar : reversedString) "foo" ['a', 'b', 'c', 'd']`

`>>>`

* Hangs forever *`foldl (+) 0 [1..]`

foldl1 :: HasCallStack => (a -> a -> a) -> [a] -> a Source #

`foldl1`

is a variant of `foldl`

that has no starting value argument,
and thus must be applied to non-empty lists. Note that unlike `foldl`

, the accumulated value must be of the same type as the list elements.

`>>>`

10`foldl1 (+) [1..4]`

`>>>`

*** Exception: Prelude.foldl1: empty list`foldl1 (+) []`

`>>>`

-8`foldl1 (-) [1..4]`

`>>>`

False`foldl1 (&&) [True, False, True, True]`

`>>>`

True`foldl1 (||) [False, False, True, True]`

`>>>`

* Hangs forever *`foldl1 (+) [1..]`

\(\mathcal{O}(1)\). Test whether a list is empty.

`>>>`

True`null []`

`>>>`

False`null [1]`

`>>>`

False`null [1..]`

\(\mathcal{O}(n)\). `length`

returns the length of a finite list as an
`Int`

. It is an instance of the more general `genericLength`

, the
result type of which may be any kind of number.

`>>>`

0`length []`

`>>>`

3`length ['a', 'b', 'c']`

`>>>`

* Hangs forever *`length [1..]`

elem :: Eq a => a -> [a] -> Bool infix 4 Source #

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

`>>>`

False`3 `elem` []`

`>>>`

False`3 `elem` [1,2]`

`>>>`

True`3 `elem` [1,2,3,4,5]`

`>>>`

True`3 `elem` [1..]`

`>>>`

* Hangs forever *`3 `elem` [4..]`

maximum :: (Ord a, HasCallStack) => [a] -> a Source #

`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 `maximumBy`

, which allows the
programmer to supply their own comparison function.

`>>>`

*** Exception: Prelude.maximum: empty list`maximum []`

`>>>`

42`maximum [42]`

`>>>`

55`maximum [55, -12, 7, 0, -89]`

`>>>`

* Hangs forever *`maximum [1..]`

minimum :: (Ord a, HasCallStack) => [a] -> a Source #

`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 `minimumBy`

, which allows the
programmer to supply their own comparison function.

`>>>`

*** Exception: Prelude.minimum: empty list`minimum []`

`>>>`

42`minimum [42]`

`>>>`

-89`minimum [55, -12, 7, 0, -89]`

`>>>`

* Hangs forever *`minimum [1..]`

sum :: Num a => [a] -> a Source #

The `sum`

function computes the sum of a finite list of numbers.

`>>>`

0`sum []`

`>>>`

42`sum [42]`

`>>>`

55`sum [1..10]`

`>>>`

7.8`sum [4.1, 2.0, 1.7]`

`>>>`

* Hangs forever *`sum [1..]`

product :: Num a => [a] -> a Source #

The `product`

function computes the product of a finite list of numbers.

`>>>`

1`product []`

`>>>`

42`product [42]`

`>>>`

3628800`product [1..10]`

`>>>`

13.939999999999998`product [4.1, 2.0, 1.7]`

`>>>`

* Hangs forever *`product [1..]`

and :: [Bool] -> Bool Source #

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

`>>>`

True`and []`

`>>>`

True`and [True]`

`>>>`

False`and [False]`

`>>>`

False`and [True, True, False]`

`>>>`

False`and (False : repeat True) -- Infinite list [False,True,True,True,True,True,True...`

`>>>`

* Hangs forever *`and (repeat True)`

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

`>>>`

False`or []`

`>>>`

True`or [True]`

`>>>`

False`or [False]`

`>>>`

True`or [True, True, False]`

`>>>`

True`or (True : repeat False) -- Infinite list [True,False,False,False,False,False,False...`

`>>>`

* Hangs forever *`or (repeat False)`

any :: (a -> Bool) -> [a] -> Bool Source #

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.

`>>>`

False`any (> 3) []`

`>>>`

False`any (> 3) [1,2]`

`>>>`

True`any (> 3) [1,2,3,4,5]`

`>>>`

True`any (> 3) [1..]`

`>>>`

* Hangs forever *`any (> 3) [0, -1..]`

all :: (a -> Bool) -> [a] -> Bool Source #

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.

`>>>`

True`all (> 3) []`

`>>>`

False`all (> 3) [1,2]`

`>>>`

False`all (> 3) [1,2,3,4,5]`

`>>>`

False`all (> 3) [1..]`

`>>>`

* Hangs forever *`all (> 3) [4..]`

foldl1' :: HasCallStack => (a -> a -> a) -> [a] -> a Source #

A strict version of `foldl1`

.

concat :: [[a]] -> [a] Source #

Concatenate a list of lists.

`>>>`

[]`concat []`

`>>>`

[42]`concat [[42]]`

`>>>`

[1,2,3,4,5,6]`concat [[1,2,3], [4,5], [6], []]`

map :: (a -> b) -> [a] -> [b] Source #

\(\mathcal{O}(n)\). `map`

`f xs`

is the list obtained by applying `f`

to
each element of `xs`

, i.e.,

map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn] map f [x1, x2, ...] == [f x1, f x2, ...]

`>>>`

[2,3,4]`map (+1) [1, 2, 3]`

(++) :: [a] -> [a] -> [a] infixr 5 Source #

Append two lists, i.e.,

[x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn] [x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...]

If the first list is not finite, the result is the first list.

This function takes linear time in the number of elements of the
**first** list. Thus it is better to associate repeated
applications of `(++)`

to the right (which is the default behaviour):
`xs ++ (ys ++ zs)`

or simply `xs ++ ys ++ zs`

, but not `(xs ++ ys) ++ zs`

.
For the same reason `concat`

`=`

`foldr`

`(++)`

`[]`

has linear performance, while `foldl`

`(++)`

`[]`

is prone
to quadratic slowdown.

filter :: (a -> Bool) -> [a] -> [a] Source #

\(\mathcal{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]

`>>>`

[1,3]`filter odd [1, 2, 3]`

head :: HasCallStack => [a] -> a Source #

Warning: This is a partial function, it throws an error on empty lists. Use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty.

\(\mathcal{O}(1)\). Extract the first element of a list, which must be non-empty.

`>>>`

1`head [1, 2, 3]`

`>>>`

1`head [1..]`

`>>>`

*** Exception: Prelude.head: empty list`head []`

WARNING: This function is partial. You can use case-matching, `uncons`

or
`listToMaybe`

instead.

last :: HasCallStack => [a] -> a Source #

\(\mathcal{O}(n)\). Extract the last element of a list, which must be finite and non-empty.

`>>>`

3`last [1, 2, 3]`

`>>>`

* Hangs forever *`last [1..]`

`>>>`

*** Exception: Prelude.last: empty list`last []`

WARNING: This function is partial. Consider using `unsnoc`

instead.

tail :: HasCallStack => [a] -> [a] Source #

Warning: This is a partial function, it throws an error on empty lists. Replace it with drop 1, or use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty.

\(\mathcal{O}(1)\). Extract the elements after the head of a list, which must be non-empty.

`>>>`

[2,3]`tail [1, 2, 3]`

`>>>`

[]`tail [1]`

`>>>`

*** Exception: Prelude.tail: empty list`tail []`

WARNING: This function is partial. You can use case-matching or `uncons`

instead.

init :: HasCallStack => [a] -> [a] Source #

\(\mathcal{O}(n)\). Return all the elements of a list except the last one. The list must be non-empty.

`>>>`

[1,2]`init [1, 2, 3]`

`>>>`

[]`init [1]`

`>>>`

*** Exception: Prelude.init: empty list`init []`

WARNING: This function is partial. Consider using `unsnoc`

instead.

unsnoc :: [a] -> Maybe ([a], a) Source #

\(\mathcal{O}(n)\). Decompose a list into `init`

and `last`

.

- If the list is empty, returns
`Nothing`

. - If the list is non-empty, returns

, where`Just`

(xs, x)`xs`

is the`init`

ial part of the list and`x`

is its`last`

element.

`>>>`

Nothing`unsnoc []`

`>>>`

Just ([],1)`unsnoc [1]`

`>>>`

Just ([1,2],3)`unsnoc [1, 2, 3]`

Laziness:

`>>>`

Just []`fst <$> unsnoc [undefined]`

`>>>`

Just *** Exception: Prelude.undefined`head . fst <$> unsnoc (1 : undefined)`

`>>>`

Just 1`head . fst <$> unsnoc (1 : 2 : undefined)`

`unsnoc`

is dual to `uncons`

: for a finite list `xs`

unsnoc xs = (\(hd, tl) -> (reverse tl, hd)) <$> uncons (reverse xs)

*Since: base-4.19.0.0*

(!?) :: [a] -> Int -> Maybe a infixl 9 Source #

List index (subscript) operator, starting from 0. Returns `Nothing`

if the index is out of bounds

`>>>`

Just 'a'`['a', 'b', 'c'] !? 0`

`>>>`

Just 'c'`['a', 'b', 'c'] !? 2`

`>>>`

Nothing`['a', 'b', 'c'] !? 3`

`>>>`

Nothing`['a', 'b', 'c'] !? (-1)`

This is the total variant of the partial `!!`

operator.

WARNING: This function takes linear time in the index.

(!!) :: HasCallStack => [a] -> Int -> a infixl 9 Source #

List index (subscript) operator, starting from 0.
It is an instance of the more general `genericIndex`

,
which takes an index of any integral type.

`>>>`

'a'`['a', 'b', 'c'] !! 0`

`>>>`

'c'`['a', 'b', 'c'] !! 2`

`>>>`

*** Exception: Prelude.!!: index too large`['a', 'b', 'c'] !! 3`

`>>>`

*** Exception: Prelude.!!: negative index`['a', 'b', 'c'] !! (-1)`

WARNING: This function is partial, and should only be used if you are
sure that the indexing will not fail. Otherwise, use `!?`

.

WARNING: This function takes linear time in the index.

scanl :: (b -> a -> b) -> b -> [a] -> [b] Source #

\(\mathcal{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

`>>>`

[0,1,3,6,10]`scanl (+) 0 [1..4]`

`>>>`

[42]`scanl (+) 42 []`

`>>>`

[100,99,97,94,90]`scanl (-) 100 [1..4]`

`>>>`

["foo","afoo","bafoo","cbafoo","dcbafoo"]`scanl (\reversedString nextChar -> nextChar : reversedString) "foo" ['a', 'b', 'c', 'd']`

`>>>`

[0,1,3,6,10,15,21,28,36,45]`take 10 (scanl (+) 0 [1..])`

`>>>`

"a"`take 1 (scanl undefined 'a' undefined)`

scanl1 :: (a -> a -> a) -> [a] -> [a] Source #

\(\mathcal{O}(n)\). `scanl1`

is a variant of `scanl`

that has no starting
value argument:

scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]

`>>>`

[1,3,6,10]`scanl1 (+) [1..4]`

`>>>`

[]`scanl1 (+) []`

`>>>`

[1,-1,-4,-8]`scanl1 (-) [1..4]`

`>>>`

[True,False,False,False]`scanl1 (&&) [True, False, True, True]`

`>>>`

[False,False,True,True]`scanl1 (||) [False, False, True, True]`

`>>>`

[1,3,6,10,15,21,28,36,45,55]`take 10 (scanl1 (+) [1..])`

`>>>`

"a"`take 1 (scanl1 undefined ('a' : undefined))`

scanr :: (a -> b -> b) -> b -> [a] -> [b] Source #

\(\mathcal{O}(n)\). `scanr`

is the right-to-left dual of `scanl`

. Note that the order of parameters on the accumulating function are reversed compared to `scanl`

.
Also note that

head (scanr f z xs) == foldr f z xs.

`>>>`

[10,9,7,4,0]`scanr (+) 0 [1..4]`

`>>>`

[42]`scanr (+) 42 []`

`>>>`

[98,-97,99,-96,100]`scanr (-) 100 [1..4]`

`>>>`

["abcdfoo","bcdfoo","cdfoo","dfoo","foo"]`scanr (\nextChar reversedString -> nextChar : reversedString) "foo" ['a', 'b', 'c', 'd']`

`>>>`

*** Exception: stack overflow`force $ scanr (+) 0 [1..]`

scanr1 :: (a -> a -> a) -> [a] -> [a] Source #

\(\mathcal{O}(n)\). `scanr1`

is a variant of `scanr`

that has no starting
value argument.

`>>>`

[10,9,7,4]`scanr1 (+) [1..4]`

`>>>`

[]`scanr1 (+) []`

`>>>`

[-2,3,-1,4]`scanr1 (-) [1..4]`

`>>>`

[False,False,True,True]`scanr1 (&&) [True, False, True, True]`

`>>>`

[True,True,False,False]`scanr1 (||) [True, True, False, False]`

`>>>`

*** Exception: stack overflow`force $ scanr1 (+) [1..]`

iterate :: (a -> a) -> a -> [a] Source #

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

`>>>`

[True,False,True,False,True,False,True,False,True,False]`take 10 $ iterate not True`

`>>>`

[42,45,48,51,54,57,60,63,66,69]`take 10 $ iterate (+3) 42`

`>>>`

[42]`take 1 $ iterate undefined 42`

`repeat`

`x`

is an infinite list, with `x`

the value of every element.

`>>>`

[17,17,17,17,17,17,17,17,17...`repeat 17`

replicate :: Int -> a -> [a] Source #

`replicate`

`n x`

is a list of length `n`

with `x`

the value of
every element.
It is an instance of the more general `genericReplicate`

,
in which `n`

may be of any integral type.

`>>>`

[]`replicate 0 True`

`>>>`

[]`replicate (-1) True`

`>>>`

[True,True,True,True]`replicate 4 True`

cycle :: HasCallStack => [a] -> [a] Source #

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

`>>>`

*** Exception: Prelude.cycle: empty list`cycle []`

`>>>`

[42,42,42,42,42,42,42,42,42,42]`take 10 (cycle [42])`

`>>>`

[2,5,7,2,5,7,2,5,7,2]`take 10 (cycle [2, 5, 7])`

`>>>`

[42]`take 1 (cycle (42 : undefined))`

take :: Int -> [a] -> [a] Source #

`take`

`n`

, applied to a list `xs`

, returns the prefix of `xs`

of length `n`

, or `xs`

itself if `n >= `

.`length`

xs

`>>>`

"Hello"`take 5 "Hello World!"`

`>>>`

[1,2,3]`take 3 [1,2,3,4,5]`

`>>>`

[1,2]`take 3 [1,2]`

`>>>`

[]`take 3 []`

`>>>`

[]`take (-1) [1,2]`

`>>>`

[]`take 0 [1,2]`

Laziness:

`>>>`

[]`take 0 undefined`

`>>>`

[1]`take 1 (1 : undefined)`

It is an instance of the more general `genericTake`

,
in which `n`

may be of any integral type.

drop :: Int -> [a] -> [a] Source #

`drop`

`n xs`

returns the suffix of `xs`

after the first `n`

elements, or `[]`

if `n >= `

.`length`

xs

`>>>`

"World!"`drop 6 "Hello World!"`

`>>>`

[4,5]`drop 3 [1,2,3,4,5]`

`>>>`

[]`drop 3 [1,2]`

`>>>`

[]`drop 3 []`

`>>>`

[1,2]`drop (-1) [1,2]`

`>>>`

[1,2]`drop 0 [1,2]`

It is an instance of the more general `genericDrop`

,
in which `n`

may be of any integral type.

splitAt :: Int -> [a] -> ([a], [a]) Source #

`splitAt`

`n xs`

returns a tuple where first element is `xs`

prefix of
length `n`

and second element is the remainder of the list:

`>>>`

("Hello ","World!")`splitAt 6 "Hello World!"`

`>>>`

([1,2,3],[4,5])`splitAt 3 [1,2,3,4,5]`

`>>>`

([1],[2,3])`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]`

It is equivalent to `(`

unless `take`

n xs, `drop`

n xs)`n`

is `_|_`

:
`splitAt _|_ xs = _|_`

, not `(_|_, _|_)`

).

The first component of the tuple is produced lazily:

`>>>`

[]`fst (splitAt 0 undefined)`

`>>>`

[1]`take 1 (fst (splitAt 10 (1 : undefined)))`

`splitAt`

is an instance of the more general `genericSplitAt`

,
in which `n`

may be of any integral type.

takeWhile :: (a -> Bool) -> [a] -> [a] Source #

`takeWhile`

, applied to a predicate `p`

and a list `xs`

, returns the
longest prefix (possibly empty) of `xs`

of elements that satisfy `p`

.

`>>>`

[1,2]`takeWhile (< 3) [1,2,3,4,1,2,3,4]`

`>>>`

[1,2,3]`takeWhile (< 9) [1,2,3]`

`>>>`

[]`takeWhile (< 0) [1,2,3]`

Laziness:

`>>>`

*** Exception: Prelude.undefined`takeWhile (const False) undefined`

`>>>`

[]`takeWhile (const False) (undefined : undefined)`

`>>>`

[1]`take 1 (takeWhile (const True) (1 : undefined))`

span :: (a -> Bool) -> [a] -> ([a], [a]) Source #

`span`

, applied to a predicate `p`

and a list `xs`

, returns a tuple where
first element is the longest prefix (possibly empty) of `xs`

of elements that
satisfy `p`

and second element is the remainder of the list:

`>>>`

([1,2],[3,4,1,2,3,4])`span (< 3) [1,2,3,4,1,2,3,4]`

`>>>`

([1,2,3],[])`span (< 9) [1,2,3]`

`>>>`

([],[1,2,3])`span (< 0) [1,2,3]`

`span`

`p xs`

is equivalent to `(`

, even if `takeWhile`

p xs, `dropWhile`

p xs)`p`

is `_|_`

.

Laziness:

`>>>`

([],[])`span undefined []`

`>>>`

*** Exception: Prelude.undefined`fst (span (const False) undefined)`

`>>>`

[]`fst (span (const False) (undefined : undefined))`

`>>>`

[1]`take 1 (fst (span (const True) (1 : undefined)))`

`span`

produces the first component of the tuple lazily:

`>>>`

[1,2,3,4,5,6,7,8,9,10]`take 10 (fst (span (const True) [1..]))`

break :: (a -> Bool) -> [a] -> ([a], [a]) Source #

`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:

`>>>`

([1,2,3],[4,1,2,3,4])`break (> 3) [1,2,3,4,1,2,3,4]`

`>>>`

([],[1,2,3])`break (< 9) [1,2,3]`

`>>>`

([1,2,3],[])`break (> 9) [1,2,3]`

`break`

`p`

is equivalent to

and consequently to `span`

(`not`

. p)`(`

,
even if `takeWhile`

(`not`

. p) xs, `dropWhile`

(`not`

. p) xs)`p`

is `_|_`

.

Laziness:

`>>>`

([],[])`break undefined []`

`>>>`

*** Exception: Prelude.undefined`fst (break (const True) undefined)`

`>>>`

[]`fst (break (const True) (undefined : undefined))`

`>>>`

[1]`take 1 (fst (break (const False) (1 : undefined)))`

`break`

produces the first component of the tuple lazily:

`>>>`

[1,2,3,4,5,6,7,8,9,10]`take 10 (fst (break (const False) [1..]))`

reverse :: [a] -> [a] Source #

`reverse`

`xs`

returns the elements of `xs`

in reverse order.
`xs`

must be finite.

`>>>`

[]`reverse []`

`>>>`

[42]`reverse [42]`

`>>>`

[7,5,2]`reverse [2,5,7]`

`>>>`

* Hangs forever *`reverse [1..]`

zip :: [a] -> [b] -> [(a, b)] Source #

\(\mathcal{O}(\min(m,n))\). `zip`

takes two lists and returns a list of
corresponding pairs.

`>>>`

[(1,'a'),(2,'b')]`zip [1, 2] ['a', 'b']`

If one input list is shorter than the other, excess elements of the longer list are discarded, even if one of the lists is infinite:

`>>>`

[(1,'a')]`zip [1] ['a', 'b']`

`>>>`

[(1,'a')]`zip [1, 2] ['a']`

`>>>`

[]`zip [] [1..]`

`>>>`

[]`zip [1..] []`

`zip`

is right-lazy:

`>>>`

[]`zip [] undefined`

`>>>`

*** Exception: Prelude.undefined ...`zip undefined []`

`zip`

is capable of list fusion, but it is restricted to its
first list argument and its resulting list.

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] Source #

\(\mathcal{O}(\min(m,n))\). `zipWith`

generalises `zip`

by zipping with the
function given as the first argument, instead of a tupling function.

zipWith (,) xs ys == zip xs ys zipWith f [x1,x2,x3..] [y1,y2,y3..] == [f x1 y1, f x2 y2, f x3 y3..]

For example,

is applied to two lists to produce the list of
corresponding sums:`zipWith`

(+)

`>>>`

[5,7,9]`zipWith (+) [1, 2, 3] [4, 5, 6]`

`zipWith`

is right-lazy:

`>>>`

`let f = undefined`

`>>>`

[]`zipWith f [] undefined`

`zipWith`

is capable of list fusion, but it is restricted to its
first list argument and its resulting list.

zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d] Source #

The `zipWith3`

function takes a function which combines three
elements, as well as three lists and returns a list of the function applied
to corresponding elements, analogous to `zipWith`

.
It is capable of list fusion, but it is restricted to its
first list argument and its resulting list.

zipWith3 (,,) xs ys zs == zip3 xs ys zs zipWith3 f [x1,x2,x3..] [y1,y2,y3..] [z1,z2,z3..] == [f x1 y1 z1, f x2 y2 z2, f x3 y3 z3..]

unzip :: [(a, b)] -> ([a], [b]) Source #

`unzip`

transforms a list of pairs into a list of first components
and a list of second components.

`>>>`

([],[])`unzip []`

`>>>`

([1,2],"ab")`unzip [(1, 'a'), (2, 'b')]`

errorEmptyList :: HasCallStack => String -> a Source #