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

- map :: (a -> b) -> [a] -> [b]
- (++) :: [a] -> [a] -> [a]
- filter :: (a -> Bool) -> [a] -> [a]
- concat :: [[a]] -> [a]
- head :: [a] -> a
- last :: [a] -> a
- tail :: [a] -> [a]
- init :: [a] -> [a]
- uncons :: [a] -> Maybe (a, [a])
- null :: [a] -> Bool
- length :: [a] -> Int
- (!!) :: [a] -> Int -> a
- foldl :: forall a b. (b -> a -> b) -> b -> [a] -> b
- foldl' :: forall a b. (b -> a -> b) -> b -> [a] -> b
- foldl1 :: (a -> a -> a) -> [a] -> a
- foldl1' :: (a -> a -> a) -> [a] -> a
- scanl :: (b -> a -> b) -> b -> [a] -> [b]
- scanl1 :: (a -> a -> a) -> [a] -> [a]
- scanl' :: (b -> a -> b) -> b -> [a] -> [b]
- foldr :: (a -> b -> b) -> b -> [a] -> b
- foldr1 :: (a -> a -> a) -> [a] -> a
- 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 :: [a] -> [a]
- take :: Int -> [a] -> [a]
- drop :: Int -> [a] -> [a]
- sum :: Num a => [a] -> a
- product :: Num a => [a] -> a
- maximum :: Ord a => [a] -> a
- minimum :: Ord a => [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]
- and :: [Bool] -> Bool
- or :: [Bool] -> Bool
- any :: (a -> Bool) -> [a] -> Bool
- all :: (a -> Bool) -> [a] -> Bool
- elem :: Eq a => a -> [a] -> Bool
- notElem :: Eq a => a -> [a] -> Bool
- lookup :: Eq a => a -> [(a, b)] -> Maybe b
- concatMap :: (a -> [b]) -> [a] -> [b]
- 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 :: String -> a

# Documentation

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.

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

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], []]`

\(\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 []`

\(\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 []`

\(\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 []`

\(\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 []`

\(\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..]`

(!!) :: [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)`

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 :: (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..]`

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

`>>>`

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

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

`>>>`

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

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

foldr1 :: (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..]`

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...`take 10 $ iterate not True`

`>>>`

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

`repeat`

`x`

is an infinite list, with `x`

the value of every element.

`>>>`

[17,17,17,17,17,17,17,17,17...`take 20 $ 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`

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 20 $ cycle [42]`

`>>>`

[2,5,7,2,5,7,2,5,7,2,5,7...`take 20 $ cycle [2, 5, 7]`

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

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.

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

maximum :: Ord a => [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 => [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..]`

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

when `take`

n xs, `drop`

n xs)`n`

is not `_|_`

(`splitAt _|_ xs = _|_`

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

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

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

`>>>`

([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]`

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

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

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

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

lookup :: Eq a => a -> [(a, b)] -> Maybe b Source #

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

`key assocs`

looks up a key in an association
list.

`>>>`

Nothing`lookup 2 []`

`>>>`

Nothing`lookup 2 [(1, "first")]`

`>>>`

Just "second"`lookup 2 [(1, "first"), (2, "second"), (3, "third")]`

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 :: String -> a Source #