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, ...]
>>>
map (+1) [1, 2, 3]
[2,3,4]
(++) :: [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]
>>>
filter odd [1, 2, 3]
[1,3]
concat :: [[a]] -> [a] Source #
Concatenate a list of lists.
>>>
concat []
[]>>>
concat [[42]]
[42]>>>
concat [[1,2,3], [4,5], [6], []]
[1,2,3,4,5,6]
\(\mathcal{O}(1)\). Extract the first element of a list, which must be non-empty.
>>>
head [1, 2, 3]
1>>>
head [1..]
1>>>
head []
Exception: Prelude.head: empty list
\(\mathcal{O}(n)\). Extract the last element of a list, which must be finite and non-empty.
>>>
last [1, 2, 3]
3>>>
last [1..]
* Hangs forever *>>>
last []
Exception: Prelude.last: empty list
\(\mathcal{O}(1)\). Extract the elements after the head of a list, which must be non-empty.
>>>
tail [1, 2, 3]
[2,3]>>>
tail [1]
[]>>>
tail []
Exception: Prelude.tail: empty list
\(\mathcal{O}(n)\). Return all the elements of a list except the last one. The list must be non-empty.
>>>
init [1, 2, 3]
[1,2]>>>
init [1]
[]>>>
init []
Exception: Prelude.init: empty list
\(\mathcal{O}(1)\). Test whether a list is empty.
>>>
null []
True>>>
null [1]
False>>>
null [1..]
False
\(\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.
>>>
length []
0>>>
length ['a', 'b', 'c']
3>>>
length [1..]
* Hangs forever *
(!!) :: [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', 'b', 'c'] !! 0
'a'>>>
['a', 'b', 'c'] !! 2
'c'>>>
['a', 'b', 'c'] !! 3
Exception: Prelude.!!: index too large>>>
['a', 'b', 'c'] !! (-1)
Exception: Prelude.!!: negative index
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.
>>>
foldl (+) 0 [1..4]
10>>>
foldl (+) 42 []
42>>>
foldl (-) 100 [1..4]
90>>>
foldl (\reversedString nextChar -> nextChar : reversedString) "foo" ['a', 'b', 'c', 'd']
"dcbafoo">>>
foldl (+) 0 [1..]
* Hangs forever *
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.
>>>
foldl1 (+) [1..4]
10>>>
foldl1 (+) []
Exception: Prelude.foldl1: empty list>>>
foldl1 (-) [1..4]
-8>>>
foldl1 (&&) [True, False, True, True]
False>>>
foldl1 (||) [False, False, True, True]
True>>>
foldl1 (+) [1..]
* Hangs forever *
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
>>>
scanl (+) 0 [1..4]
[0,1,3,6,10]>>>
scanl (+) 42 []
[42]>>>
scanl (-) 100 [1..4]
[100,99,97,94,90]>>>
scanl (\reversedString nextChar -> nextChar : reversedString) "foo" ['a', 'b', 'c', 'd']
["foo","afoo","bafoo","cbafoo","dcbafoo"]>>>
scanl (+) 0 [1..]
* Hangs forever *
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, ...]
>>>
scanl1 (+) [1..4]
[1,3,6,10]>>>
scanl1 (+) []
[]>>>
scanl1 (-) [1..4]
[1,-1,-4,-8]>>>
scanl1 (&&) [True, False, True, True]
[True,False,False,False]>>>
scanl1 (||) [False, False, True, True]
[False,False,True,True]>>>
scanl1 (+) [1..]
* Hangs forever *
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.
>>>
foldr1 (+) [1..4]
10>>>
foldr1 (+) []
Exception: Prelude.foldr1: empty list>>>
foldr1 (-) [1..4]
-2>>>
foldr1 (&&) [True, False, True, True]
False>>>
foldr1 (||) [False, False, True, True]
True>>>
foldr1 (+) [1..]
* Hangs forever *
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.
>>>
scanr (+) 0 [1..4]
[10,9,7,4,0]>>>
scanr (+) 42 []
[42]>>>
scanr (-) 100 [1..4]
[98,-97,99,-96,100]>>>
scanr (\nextChar reversedString -> nextChar : reversedString) "foo" ['a', 'b', 'c', 'd']
["abcdfoo","bcdfoo","cdfoo","dfoo","foo"]>>>
scanr (+) 0 [1..]
* Hangs forever *
scanr1 :: (a -> a -> a) -> [a] -> [a] Source #
\(\mathcal{O}(n)\). scanr1
is a variant of scanr
that has no starting
value argument.
>>>
scanr1 (+) [1..4]
[10,9,7,4]>>>
scanr1 (+) []
[]>>>
scanr1 (-) [1..4]
[-2,3,-1,4]>>>
scanr1 (&&) [True, False, True, True]
[False,False,True,True]>>>
scanr1 (||) [True, True, False, False]
[True,True,False,False]>>>
scanr1 (+) [1..]
* Hangs forever *
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.
>>>
iterate not True
[True,False,True,False...>>>
iterate (+3) 42
[42,45,48,51,54,57,60,63...
repeat
x
is an infinite list, with x
the value of every element.
>>>
repeat 17
[17,17,17,17,17,17,17,17,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
[]>>>
replicate 4 True
[True,True,True,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.
>>>
cycle []
Exception: Prelude.cycle: empty list>>>
cycle [42]
[42,42,42,42,42,42,42,42,42,42...>>>
cycle [2, 5, 7]
[2,5,7,2,5,7,2,5,7,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
>>>
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 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
>>>
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 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.
>>>
sum []
0>>>
sum [42]
42>>>
sum [1..10]
55>>>
sum [4.1, 2.0, 1.7]
7.8>>>
sum [1..]
* Hangs forever *
product :: Num a => [a] -> a Source #
The product
function computes the product of a finite list of numbers.
>>>
product []
1>>>
product [42]
42>>>
product [1..10]
3628800>>>
product [4.1, 2.0, 1.7]
13.939999999999998>>>
product [1..]
* Hangs forever *
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.
>>>
maximum []
Exception: Prelude.maximum: empty list>>>
maximum [42]
42>>>
maximum [55, -12, 7, 0, -89]
55>>>
maximum [1..]
* Hangs forever *
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.
>>>
minimum []
Exception: Prelude.minimum: empty list>>>
minimum [42]
42>>>
minimum [55, -12, 7, 0, -89]
-89>>>
minimum [1..]
* Hangs forever *
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:
>>>
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 (
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
.
>>>
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]
[]
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:
>>>
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])
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:
>>>
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],[])
reverse :: [a] -> [a] Source #
reverse
xs
returns the elements of xs
in reverse order.
xs
must be finite.
>>>
reverse []
[]>>>
reverse [42]
[42]>>>
reverse [2,5,7]
[7,5,2]>>>
reverse [1..]
* Hangs forever *
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.
>>>
and []
True>>>
and [True]
True>>>
and [False]
False>>>
and [True, True, False]
False>>>
and (False : repeat True) -- Infinite list [False,True,True,True,True,True,True...
False>>>
and (repeat True)
* Hangs forever *
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 []
False>>>
or [True]
True>>>
or [False]
False>>>
or [True, True, False]
True>>>
or (True : repeat False) -- Infinite list [True,False,False,False,False,False,False...
True>>>
or (repeat False)
* Hangs forever *
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.
>>>
any (> 3) []
False>>>
any (> 3) [1,2]
False>>>
any (> 3) [1,2,3,4,5]
True>>>
any (> 3) [1..]
True>>>
any (> 3) [0, -1..]
* Hangs forever *
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.
>>>
all (> 3) []
True>>>
all (> 3) [1,2]
False>>>
all (> 3) [1,2,3,4,5]
False>>>
all (> 3) [1..]
False>>>
all (> 3) [4..]
* Hangs forever *
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.
>>>
3 `elem` []
False>>>
3 `elem` [1,2]
False>>>
3 `elem` [1,2,3,4,5]
True>>>
3 `elem` [1..]
True>>>
3 `elem` [4..]
* Hangs forever *
lookup :: Eq a => a -> [(a, b)] -> Maybe b Source #
\(\mathcal{O}(n)\). lookup
key assocs
looks up a key in an association
list.
>>>
lookup 2 []
Nothing>>>
lookup 2 [(1, "first")]
Nothing>>>
lookup 2 [(1, "first"), (2, "second"), (3, "third")]
Just "second"
zip :: [a] -> [b] -> [(a, b)] Source #
\(\mathcal{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 shorter than the other, excess elements of the longer list are discarded, even if one of the lists is infinite:
>>>
zip [1] ['a', 'b']
[(1, 'a')]>>>
zip [1, 2] ['a']
[(1, 'a')]>>>
zip [] [1..]
[]>>>
zip [1..] []
[]
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.
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
(+)
>>>
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.
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 []
([],[])>>>
unzip [(1, 'a'), (2, 'b')]
([1,2],"ab")
errorEmptyList :: String -> a Source #