# 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 (, [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.