Module Data.List

Library with some useful operations on lists.

Author: Michael Hanus, Bjoern Peemoeller

Version: November 2020

Summary of exported operations:

elemIndex :: Eq a => a -> [a] -> Maybe Int  Deterministic 
Returns the index i of the first occurrence of an element in a list as (Just i), otherwise Nothing is returned.
elemIndices :: Eq a => a -> [a] -> [Int]  Deterministic 
Returns the list of indices of occurrences of an element in a list.
find :: (a -> Bool) -> [a] -> Maybe a  Deterministic 
Returns the first element e of a list satisfying a predicate as (Just e), otherwise Nothing is returned.
findIndex :: (a -> Bool) -> [a] -> Maybe Int  Deterministic 
Returns the index i of the first occurrences of a list element satisfying a predicate as (Just i), otherwise Nothing is returned.
findIndices :: (a -> Bool) -> [a] -> [Int]  Deterministic 
Returns the list of indices of list elements satisfying a predicate.
nub :: Eq a => [a] -> [a]  Deterministic 
Removes all duplicates in the argument list.
nubBy :: (a -> a -> Bool) -> [a] -> [a]  Deterministic 
Removes all duplicates in the argument list according to an equivalence relation.
delete :: Eq a => a -> [a] -> [a]  Deterministic 
Deletes the first occurrence of an element in a list.
deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]  Deterministic 
Deletes the first occurrence of an element in a list according to an equivalence relation.
(\\) :: Eq a => [a] -> [a] -> [a]  Deterministic 
Computes the difference of two lists.
union :: Eq a => [a] -> [a] -> [a]  Deterministic 
Computes the union of two lists.
unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]  Deterministic 
Computes the union of two lists according to the given equivalence relation
intersect :: Eq a => [a] -> [a] -> [a]  Deterministic 
Computes the intersection of two lists.
intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]  Deterministic 
Computes the intersection of two lists according to the given equivalence relation
intersperse :: a -> [a] -> [a]  Deterministic 
Puts a separator element between all elements in a list.
intercalate :: [a] -> [[a]] -> [a]  Deterministic 
intercalate xs xss is equivalent to (concat (intersperse xs xss)).
transpose :: [[a]] -> [[a]]  Deterministic 
Transposes the rows and columns of the argument.
diagonal :: [[a]] -> [a]  Deterministic 
Diagonalization of a list of lists.
permutations :: [a] -> [[a]]  Deterministic 
Returns the list of all permutations of the argument.
partition :: (a -> Bool) -> [a] -> ([a],[a])  Deterministic 
Partitions a list into a pair of lists where the first list contains those elements that satisfy the predicate argument and the second list contains the remaining arguments.
group :: Eq a => [a] -> [[a]]  Deterministic 
Splits the list argument into a list of lists of equal adjacent elements.
groupBy :: (a -> a -> Bool) -> [a] -> [[a]]  Deterministic 
Splits the list argument into a list of lists of related adjacent elements.
splitOn :: Eq a => [a] -> [a] -> [[a]]  Deterministic 
Breaks the second list argument into pieces separated by the first list argument, consuming the delimiter.
split :: (a -> Bool) -> [a] -> [[a]]  Deterministic 
Splits a list into components delimited by separators, where the predicate returns True for a separator element.
inits :: [a] -> [[a]]  Deterministic 
Returns all initial segments of a list, starting with the shortest.
tails :: [a] -> [[a]]  Deterministic 
Returns all final segments of a list, starting with the longest.
replace :: a -> Int -> [a] -> [a]  Deterministic 
Replaces an element in a list.
isPrefixOf :: Eq a => [a] -> [a] -> Bool  Deterministic 
Checks whether a list is a prefix of another.
isSuffixOf :: Eq a => [a] -> [a] -> Bool  Deterministic 
Checks whether a list is a suffix of another.
isInfixOf :: Eq a => [a] -> [a] -> Bool  Deterministic 
Checks whether a list is contained in another.
sort :: Ord a => [a] -> [a]  Deterministic 
The default sorting operation, mergeSort, with standard ordering <=.
sortBy :: (a -> a -> Bool) -> [a] -> [a]  Deterministic 
Sorts a list w.r.t.
insertBy :: (a -> a -> Bool) -> a -> [a] -> [a]  Deterministic 
Inserts an object into a list according to an ordering relation.
last :: [a] -> a  Deterministic 
Returns the last element of a non-empty list.
init :: [a] -> [a]  Deterministic 
Returns the input list with the last element removed.
sum :: Num a => [a] -> a  Deterministic 
Returns the sum of a list of integers.
product :: Num a => [a] -> a  Deterministic 
Returns the product of a list of integers.
maximum :: Ord a => [a] -> a  Deterministic 
Returns the maximum of a non-empty list.
maximumBy :: (a -> a -> Ordering) -> [a] -> a  Deterministic 
Returns the maximum of a non-empty list according to the given comparison function
minimum :: Ord a => [a] -> a  Deterministic 
Returns the minimum of a non-empty list.
minimumBy :: (a -> a -> Ordering) -> [a] -> a  Deterministic 
Returns the minimum of a non-empty list according to the given comparison function
scanl :: (a -> b -> a) -> a -> [b] -> [a]  Deterministic 
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, ...]
scanl1 :: (a -> a -> a) -> [a] -> [a]  Deterministic 
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]  Deterministic 
scanr is the right-to-left dual of scanl.
scanr1 :: (a -> a -> a) -> [a] -> [a]  Deterministic 
scanr1 is a variant of scanr that has no starting value argument.
mapAccumL :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])  Deterministic 
The mapAccumL function behaves like a combination of map and foldl; it applies a function to each element of a list, passing an accumulating parameter from left to right, and returning a final value of this accumulator together with the new list.
mapAccumR :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])  Deterministic 
The mapAccumR function behaves like a combination of map and foldr; it applies a function to each element of a list, passing an accumulating parameter from right to left, and returning a final value of this accumulator together with the new list.
cycle :: [a] -> [a]  Deterministic 
Builds an infinite list from a finite one.
unfoldr :: (a -> Maybe (b,a)) -> a -> [b]  Deterministic 
Builds a list from a seed value.

Exported operations:

elemIndex :: Eq a => a -> [a] -> Maybe Int  Deterministic 

Returns the index i of the first occurrence of an element in a list as (Just i), otherwise Nothing is returned.

elemIndices :: Eq a => a -> [a] -> [Int]  Deterministic 

Returns the list of indices of occurrences of an element in a list.

find :: (a -> Bool) -> [a] -> Maybe a  Deterministic 

Returns the first element e of a list satisfying a predicate as (Just e), otherwise Nothing is returned.

findIndex :: (a -> Bool) -> [a] -> Maybe Int  Deterministic 

Returns the index i of the first occurrences of a list element satisfying a predicate as (Just i), otherwise Nothing is returned.

findIndices :: (a -> Bool) -> [a] -> [Int]  Deterministic 

Returns the list of indices of list elements satisfying a predicate.

nub :: Eq a => [a] -> [a]  Deterministic 

Removes all duplicates in the argument list.

nubBy :: (a -> a -> Bool) -> [a] -> [a]  Deterministic 

Removes all duplicates in the argument list according to an equivalence relation.

delete :: Eq a => a -> [a] -> [a]  Deterministic 

Deletes the first occurrence of an element in a list.

deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]  Deterministic 

Deletes the first occurrence of an element in a list according to an equivalence relation.

(\\) :: Eq a => [a] -> [a] -> [a]  Deterministic 

Computes the difference of two lists.

Example call:
(xs \\ ys)
Parameters:
  • xs : a list
  • ys : a list
Returns:
the list where the first occurrence of each element of ys has been removed from xs
Further infos:
  • defined as non-associative infix operator with precedence 5

union :: Eq a => [a] -> [a] -> [a]  Deterministic 

Computes the union of two lists.

unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]  Deterministic 

Computes the union of two lists according to the given equivalence relation

intersect :: Eq a => [a] -> [a] -> [a]  Deterministic 

Computes the intersection of two lists.

intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]  Deterministic 

Computes the intersection of two lists according to the given equivalence relation

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

Puts a separator element between all elements in a list.

Example: (intersperse 9 [1,2,3,4]) = [1,9,2,9,3,9,4]

Further infos:
  • solution complete, i.e., able to compute all solutions

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

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

Transposes the rows and columns of the argument.

Example: (transpose [[1,2,3],[4,5,6]]) = [[1,4],[2,5],[3,6]]

diagonal :: [[a]] -> [a]  Deterministic 

Diagonalization of a list of lists. Fairly merges (possibly infinite) list of (possibly infinite) lists.

Example call:
(diagonal xss)
Parameters:
  • xss : lists of lists
Returns:
fair enumeration of all elements of inner lists of given lists

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

Returns the list of all permutations of the argument.

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

Partitions a list into a pair of lists where the first list contains those elements that satisfy the predicate argument and the second list contains the remaining arguments.

Example: (partition (<4) [8,1,5,2,4,3]) = ([1,2,3],[8,5,4])

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

Splits the list argument into a list of lists of equal adjacent elements.

Example: (group [1,2,2,3,3,3,4]) = [[1],[2,2],[3,3,3],[4]]

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

Splits the list argument into a list of lists of related adjacent elements.

Example call:
(groupBy eq xs)
Parameters:
  • eq : the relation to classify adjacent elements
  • xs : the list of elements
Returns:
the list of lists of related adjacent elements

splitOn :: Eq a => [a] -> [a] -> [[a]]  Deterministic 

Breaks the second list argument into pieces separated by the first list argument, consuming the delimiter. An empty delimiter is invalid, and will cause an error to be raised.

split :: (a -> Bool) -> [a] -> [[a]]  Deterministic 

Splits a list into components delimited by separators, where the predicate returns True for a separator element. The resulting components do not contain the separators. Two adjacent separators result in an empty component in the output.

split (==[a](#a)) "aabbaca" == ["","","bb","c",""]
split (==[a](#a)) ""        == [""]
Further infos:
  • partially defined

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

Returns all initial segments of a list, starting with the shortest. Example: inits [1,2,3] == [[],[1],[1,2],[1,2,3]]

Example call:
(inits xs)
Parameters:
  • xs : the list of elements
Returns:
the list of initial segments of the argument list

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

Returns all final segments of a list, starting with the longest. Example: tails [1,2,3] == [[1,2,3],[2,3],[3],[]]

Further infos:
  • solution complete, i.e., able to compute all solutions

replace :: a -> Int -> [a] -> [a]  Deterministic 

Replaces an element in a list.

Example call:
(replace x p ys)
Parameters:
  • x : the new element
  • p : the position of the new element (head = 0)
  • ys : the old list
Returns:
the new list where the p. element is replaced by x
Further infos:
  • partially defined

isPrefixOf :: Eq a => [a] -> [a] -> Bool  Deterministic 

Checks whether a list is a prefix of another.

Example call:
(isPrefixOf xs ys)
Parameters:
  • xs : a list
  • ys : a list
Returns:
True if xs is a prefix of ys

isSuffixOf :: Eq a => [a] -> [a] -> Bool  Deterministic 

Checks whether a list is a suffix of another.

Example call:
(isSuffixOf xs ys)
Parameters:
  • xs : a list
  • ys : a list
Returns:
True if xs is a suffix of ys

isInfixOf :: Eq a => [a] -> [a] -> Bool  Deterministic 

Checks whether a list is contained in another.

Example call:
(isInfixOf xs ys)
Parameters:
  • xs : a list
  • ys : a list
Returns:
True if xs is contained in ys

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

The default sorting operation, mergeSort, with standard ordering <=.

sortBy :: (a -> a -> Bool) -> [a] -> [a]  Deterministic 

Sorts a list w.r.t. an ordering relation by the insertion method.

insertBy :: (a -> a -> Bool) -> a -> [a] -> [a]  Deterministic 

Inserts an object into a list according to an ordering relation.

Example call:
(insertBy le x xs)
Parameters:
  • le : an ordering relation (e.g., less-or-equal)
  • x : an element
  • xs : a list
Returns:
a list where the element has been inserted

last :: [a] -> a  Deterministic 

Returns the last element of a non-empty list.

Further infos:
  • partially defined

init :: [a] -> [a]  Deterministic 

Returns the input list with the last element removed.

Further infos:
  • partially defined

sum :: Num a => [a] -> a  Deterministic 

Returns the sum of a list of integers.

product :: Num a => [a] -> a  Deterministic 

Returns the product of a list of integers.

maximum :: Ord a => [a] -> a  Deterministic 

Returns the maximum of a non-empty list.

Further infos:
  • partially defined

maximumBy :: (a -> a -> Ordering) -> [a] -> a  Deterministic 

Returns the maximum of a non-empty list according to the given comparison function

Further infos:
  • partially defined

minimum :: Ord a => [a] -> a  Deterministic 

Returns the minimum of a non-empty list.

Further infos:
  • partially defined

minimumBy :: (a -> a -> Ordering) -> [a] -> a  Deterministic 

Returns the minimum of a non-empty list according to the given comparison function

Further infos:
  • partially defined

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

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

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

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

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

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

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

mapAccumL :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])  Deterministic 

The mapAccumL function behaves like a combination of map and foldl; it applies a function to each element of a list, passing an accumulating parameter from left to right, and returning a final value of this accumulator together with the new list.

mapAccumR :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])  Deterministic 

The mapAccumR function behaves like a combination of map and foldr; it applies a function to each element of a list, passing an accumulating parameter from right to left, and returning a final value of this accumulator together with the new list.

cycle :: [a] -> [a]  Deterministic 

Builds an infinite list from a finite one.

Further infos:
  • partially defined

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

Builds a list from a seed value.