# Module DA.List¶

List

## Functions¶

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.

Elements are arranged from lowest to highest, keeping duplicates in the order they appeared in the input (a stable sort).

sortBy

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

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

minimumBy

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

minimumBy f xs returns the first element x of xs for which f x y is either LT or EQ for all other y in xs. xs must be non-empty.

maximumBy

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

maximumBy f xs returns the first element x of xs for which f x y is either GT or EQ for all other y in xs. xs must be non-empty.

sortOn

: Ord k => (a -> k) -> [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 sometimes called the decorate-sort-undecorate paradigm.

Elements are arranged from from lowest to highest, keeping duplicates in the order they appeared in the input.

minimumOn

: Ord k => (a -> k) -> [a] -> a

minimumOn f xs returns the first element x of xs for which f x is smaller than or equal to any other f y for y in xs. xs must be non-empty.

maximumOn

: Ord k => (a -> k) -> [a] -> a

maximumOn f xs returns the first element x of xs for which f x is greater than or equal to any other f y for y in xs. xs must be non-empty.

mergeBy

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

Merge two sorted lists using into a single, sorted whole, allowing the programmer to specify the comparison function.

combinePairs

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

Combine elements pairwise by means of a programmer supplied function from two list inputs into a single list.

foldBalanced1

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

Fold a non-empty list in a balanced way. Balanced means that each element has approximately the same depth in the operator tree. Approximately the same depth means that the difference between maximum and minimum depth is at most 1. The accumulation operation must be associative and commutative in order to get the same result as foldl1 or foldr1.

group

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

The ‘group’ function groups equal elements into sublists such that the concatenation of the result is equal to the argument.

groupBy

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

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

groupOn

: Eq k => (a -> k) -> [a] -> [[a]]

Similar to ‘group’, except that the equality is done on an extracted value.

dedup

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

dedup l removes duplicate elements from a list. In particular, it keeps only the first occurrence of each element. It is a special case of dedupBy, which allows the programmer to supply their own equality test. dedup is called nub in Haskell.

dedupBy

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

A version of dedup with a custom predicate.

dedupOn

: Ord k => (a -> k) -> [a] -> [a]

A version of dedup where deduplication is done after applyng function. Example use: dedupOn (.employeeNo) employees

dedupSort

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

The dedupSort function sorts and removes duplicate elements from a list. In particular, it keeps only the first occurrence of each element.

dedupSortBy

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

A version of dedupSort with a custom predicate.

unique

: Ord a => [a] -> Bool

Returns True if and only if there are no duplicate elements in the given list.

uniqueBy

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

A version of unique with a custom predicate.

uniqueOn

: Ord k => (a -> k) -> [a] -> Bool

Returns True if and only if there are no duplicate elements in the given list after applyng function. Example use: assert \$ uniqueOn (.employeeNo) employees

replace

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

Given a list and a replacement list, replaces each occurance of the search list with the replacement list in the operation list.

dropPrefix

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

Drops the given prefix from a list. It returns the original sequence if the sequence doesn’t start with the given prefix.

dropSuffix

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

Drops the given suffix from a list. It returns the original sequence if the sequence doesn’t end with the given suffix.

stripPrefix

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

The stripPrefix function drops the given prefix from a list. It returns None if the list did not start with the prefix given, or Some the list after the prefix, if it does.

stripSuffix

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

Return the prefix of the second list if its suffix matches the entire first list.

stripInfix

: Eq a => [a] -> [a] -> Optional ([a], [a])

Return the string before and after the search string or None if the search string is not found.

>>> stripInfix [0,0] [1,0,0,2,0,0,3]
Some ([1], [2,0,0,3])

>>> stripInfix [0,0] [1,2,0,4,5]
None

isPrefixOf

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

The isPrefixOf function takes two lists and returns True if and only if the first is a prefix of the second.

isSuffixOf

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

The isSuffixOf function takes two lists and returns True if and only if the first list is a suffix of the second.

isInfixOf

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

The isInfixOf function takes two lists and returns True if and only if the first list is contained anywhere within the second.

mapAccumL

: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])

The mapAccumL function combines the behaviours 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.

inits

: [a] -> [[a]]

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

intersperse

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

The intersperse function takes an element and a list and “intersperses” that element between the elements of the list.

intercalate

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

intercalate inserts the list xs in between the lists in xss and concatenates the result.

tails

: [a] -> [[a]]

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

dropWhileEnd

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

A version of dropWhile operating from the end.

takeWhileEnd

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

A version of takeWhile operating from the end.

transpose

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

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

breakEnd

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

Break, but from the end.

breakOn

: Eq a => [a] -> [a] -> ([a], [a])

Find the first instance of needle in haystack. The first element of the returned tuple is the prefix of haystack before needle is matched. The second is the remainder of haystack, starting with the match. If you want the remainder without the match, use stripInfix.

breakOnEnd

: Eq a => [a] -> [a] -> ([a], [a])

Similar to breakOn, but searches from the end of the string.

The first element of the returned tuple is the prefix of haystack up to and including the last match of needle. The second is the remainder of haystack, following the match.

linesBy

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

A variant of lines with a custom test. In particular, if there is a trailing separator it will be discarded.

wordsBy

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

A variant of words with a custom test. In particular, adjacent separators are discarded, as are leading or trailing separators.

: [a] -> a

Extract the first element of a list, which must be non-empty.

tail

: [a] -> [a]

Extract the elements after the head of a list, which must be non-empty.

last

: [a] -> a

Extract the last element of a list, which must be finite and non-empty.

init

: [a] -> [a]

Return all the elements of a list except the last one. The list must be non-empty.

foldl1

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

Left associative fold of a list that must be non-empty.

foldr1

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

Right associative fold of a list that must be non-empty.

repeatedly

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

Apply some operation repeatedly, producing an element of output and the remainder of the list.

delete

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

delete x removes the first occurrence of x from its list argument. For example,

> delete "a" ["b","a","n","a","n","a"]
["b","n","a","n","a"]


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

deleteBy

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

The ‘deleteBy’ function behaves like ‘delete’, but takes a user-supplied equality predicate.

> deleteBy (<=) 4 [1..10]
[1,2,3,5,6,7,8,9,10]

(\\)

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

The \\ function is list difference (non-associative). In the result of xs \\ ys, the first occurrence of each element of ys in turn (if any) has been removed from xs. Thus

(xs ++ ys) \\ xs == ys


Note this function is O(n*m) given lists of size n and m.

singleton

: a -> [a]

Produce a singleton list.

>>> singleton True
[True]

(!!)

: [a] -> Int -> a

List index (subscript) operator, starting from 0. For example, xs !! 2 returns the third element in xs. Raises an error if the index is not suitable for the given list. The function has complexity O(n) where n is the index given, unlike in languages such as Java where array indexing is O(1).

elemIndex

: Eq a => a -> [a] -> Optional Int

Find index of element in given list. Will return None if not found.

findIndex

: (a -> Bool) -> [a] -> Optional Int

Find index, given predicate, of first matching element. Will return None if not found.