Precursor.Data.List

Basic functions

uncons :: [a] -> Maybe (a, [a])

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

List transformations

init :: [a] -> [a]

Return all the elements of a list except the last one. If the given list is empty, returns an empty list.

>>> init [1,2,3]
[1,2]
>>> init []
[]

tail :: [a] -> [a]

Extract the elements after the head of a list. If the given list is empty, returns an empty list.

>>> tail [1,2,3]
[2,3]
>>> tail []
[]

reverse :: [a] -> [a]

reverse xs returns the elements of xs in reverse order. xs must be finite.

intersperse :: a -> [a] -> [a]

The intersperse function takes an element and a list and `intersperses' that element between the elements of the list. For example,

intersperse ',' "abcde" == "a,b,c,d,e"

intercalate :: [a] -> [[a]] -> [a]

intercalate xs xss is equivalent to (concat (intersperse xs xss)). It inserts the list xs in between the lists in xss and concatenates the result.

transpose :: [[a]] -> [[a]]

The transpose function transposes the rows and columns of its argument. For example,

transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]

If some of the rows are shorter than the following rows, their elements are skipped:

transpose [[10,11],[20],[],[30,31,32]] == [[10,20,30],[11,31],[32]]

subsequences :: [a] -> [[a]]

The subsequences function returns the list of all subsequences of the argument.

subsequences "abc" == ["","a","b","ab","c","ac","bc","abc"]

permutations :: [a] -> [[a]]

The permutations function returns the list of all permutations of the argument.

permutations "abc" == ["abc","bac","cba","bca","cab","acb"]

nub :: Ord a => [a] -> [a]

O(n*log n). The nub function removes duplicate elements from a list. In particular, it keeps only the first occurrence of each element. (The name nub means `essence'.)

>>> nub [1,2,3,2,3,4,1,2,5,2,3]
[1,2,3,4,5]
>>> take 5 (nub [1..])
[1,2,3,4,5]
>>> take 5 (nub [10,9..])
[10,9,8,7,6]

Building lists

fromList :: IsList l => [Item l] -> l

The fromList function constructs the structure l from the given list of Item l

Scans

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

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' :: (b -> a -> b) -> b -> [a] -> [b]

A strictly accumulating version of scanl

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

scanl1 is a variant of scanl that has no starting value argument:

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

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

scanr is the right-to-left dual of scanl. Note that

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

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

scanr1 is a variant of scanr that has no starting value argument.

Infinite lists

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

iterate f x returns an infinite list of repeated applications of f to x:

iterate f x == [x, f x, f (f x), ...]

repeat :: a -> [a]

repeat x is an infinite list, with x the value of every element.

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

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.

cycle :: [a] -> [a]

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.

Unfolding

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

The unfoldr function is a `dual' to foldr: while foldr reduces a list to a summary value, unfoldr builds a list from a seed value. The function takes the element and returns Nothing if it is done producing the list or returns Just (a,b), in which case, a is a prepended to the list and b is used as the next element in a recursive call. For example,

iterate f == unfoldr (\x -> Just (x, f x))

In some cases, unfoldr can undo a foldr operation:

unfoldr f' (foldr f z xs) == xs

if the following holds:

f' (f x y) = Just (x,y)
f' z       = Nothing

A simple use of unfoldr:

unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
 [10,9,8,7,6,5,4,3,2,1]

unfoldl :: (b -> Maybe (b, a)) -> b -> [a]

unfoldl is the dual of foldl, similar to unfoldr. It can be quite useful as a kind of lightweight state-thing:

>>> let toDigs b = unfoldl (ensure (>0) >-> flip divMod b)
>>> toDigs 10 123
[1,2,3]
>>> toDigs 2 5
[1,0,1]

Sublists

Extracting sublists

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

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]

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.

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

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 genericSplitAt, in which n may be of any integral type.

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

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] == []

dropWhile :: (a -> Bool) -> [a] -> [a]

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]

group :: Eq a => [a] -> [[a]]

The group function takes a list and returns a list of lists such that the concatenation of the result is equal to the argument. Moreover, each sublist in the result contains only equal elements. For example,

group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]

It is a special case of groupBy, which allows the programmer to supply their own equality test.

inits :: [a] -> [[a]]

The inits function returns all initial segments of the argument, shortest first. For example,

inits "abc" == ["","a","ab","abc"]

Note that inits has the following strictness property: inits (xs ++ _|_) = inits xs ++ _|_

In particular, inits _|_ = [] : _|_

tails :: [a] -> [[a]]

The tails function returns all final segments of the argument, longest first. For example,

tails "abc" == ["abc", "bc", "c",""]

Note that tails has the following strictness property: tails _|_ = _|_ : _|_

Searching with a predicate

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

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]

partition :: (a -> Bool) -> [a] -> ([a], [a])

The partition function takes a predicate a list and returns the pair of lists of elements which do and do not satisfy the predicate, respectively; i.e.,

partition p xs == (filter p xs, filter (not . p) xs)

Zipping and unzipping lists

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

zip takes two lists and returns a list of corresponding pairs. If one input list is short, excess elements of the longer list are discarded.

zip is right-lazy:

zip [] _|_ = []

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

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 is right-lazy:

zipWith f [] _|_ = []

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

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

zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]

zip3 takes three lists and returns a list of triples, analogous to zip.

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

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.

unzip3 :: [(a, b, c)] -> ([a], [b], [c])

The unzip3 function takes a list of triples and returns three lists, analogous to unzip.

Ordered lists

sort :: Ord a => [a] -> [a]

The sort function implements a stable sorting algorithm. It is a special case of sortBy, which allows the programmer to supply their own comparison function.

sortOn :: Ord b => (a -> b) -> [a] -> [a]

Sort a list by comparing the results of a key function applied to each element. sortOn f is equivalent to sortBy (comparing f), but has the performance advantage of only evaluating f once for each element in the input list. This is called the decorate-sort-undecorate paradigm, or Schwartzian transform.

Since: 4.8.0.0

Generalized functions

The predicate is assumed to define an equivalence.

groupBy :: (a -> a -> Bool) -> [a] -> [[a]]

The groupBy function is the non-overloaded version of group.

The function is assumed to define a total ordering.

sortBy :: (a -> a -> Ordering) -> [a] -> [a]

The sortBy function is the non-overloaded version of sort.