Safe Haskell | Safe-Inferred |
---|

Functions to operate on lists.

## Synopsis

- type NonNull a = [a]
- head :: [a] -> Maybe.Maybe a
- tail :: [a] -> Maybe.Maybe [a]
- last :: [a] -> Maybe.Maybe a
- unsnoc :: [a] -> Maybe.Maybe ([a], a)
- at :: [a] -> Int -> Maybe.Maybe a
- insertAt :: Int -> a -> [a] -> [a]
- removeAt :: Int -> [a] -> [a]
- takeAt :: Int -> [a] -> Maybe.Maybe (a, [a])
- modifyAt :: Int -> (a -> a) -> [a] -> [a]
- findModify :: (a -> Bool) -> (a -> a) -> [a] -> Maybe.Maybe [a]
- updateAt :: a -> Int -> (Maybe.Maybe a -> a) -> [a] -> [a]
- move :: Int -> Int -> [a] -> Maybe.Maybe [a]
- range :: (Num a, Ord.Ord a) => a -> a -> a -> [a]
- range' :: (Num a, Ord.Ord a) => a -> a -> a -> [a]
- rangeEnd :: (Num a, Ord.Ord a) => a -> a -> a -> [a]
- range_ :: Num a => a -> a -> [a]
- keyOn :: (a -> k) -> [a] -> [(k, a)]
- keyOnSnd :: (a -> k) -> [a] -> [(a, k)]
- keyOnJust :: (a -> Maybe.Maybe k) -> [a] -> [(k, a)]
- firstLast :: (a -> a) -> (a -> a) -> [a] -> [a]
- mapMaybeFst :: (a -> Maybe.Maybe a2) -> [(a, b)] -> [(a2, b)]
- mapMaybeSnd :: (b -> Maybe.Maybe b2) -> [(a, b)] -> [(a, b2)]
- mapHead :: (a -> a) -> [a] -> [a]
- mapTail :: (a -> a) -> [a] -> [a]
- mapHeadTail :: (a -> b) -> (a -> b) -> [a] -> [b]
- mapInit :: (a -> a) -> [a] -> [a]
- mapLast :: (a -> a) -> [a] -> [a]
- scanlOn :: (accum -> key -> accum) -> (a -> key) -> accum -> [a] -> [(accum, a)]
- minOn :: Ord.Ord k => (a -> k) -> a -> a -> a
- maxOn :: Ord.Ord k => (a -> k) -> a -> a -> a
- minimumOn :: Ord.Ord k => (a -> k) -> [a] -> Maybe.Maybe a
- maximumOn :: Ord.Ord k => (a -> k) -> [a] -> Maybe.Maybe a
- minimum :: Ord.Ord a => [a] -> Maybe.Maybe a
- maximum :: Ord.Ord a => [a] -> Maybe.Maybe a
- insertOn :: Ord.Ord k => (a -> k) -> a -> [a] -> [a]
- sortOn :: Ord.Ord k => (a -> k) -> [a] -> [a]
- reverseSortOn :: Ord.Ord b => (a -> b) -> [a] -> [a]
- merge :: Ord.Ord a => [a] -> [a] -> [a]
- mergeBy :: (a -> a -> Ord.Ordering) -> [a] -> [a] -> [a]
- mergeOn :: Ord.Ord k => (a -> k) -> [a] -> [a] -> [a]
- mergeLists :: Ord.Ord k => (a -> k) -> [[a]] -> [a]
- mergeAscLists :: Ord.Ord k => (a -> k) -> [[a]] -> [a]
- groupAdjacent :: Eq key => (a -> key) -> [a] -> [NonNull a]
- keyedGroupAdjacent :: Eq key => (a -> key) -> [a] -> [(key, NonNull a)]
- groupAdjacentFst :: Eq a => [(a, b)] -> [(a, NonNull b)]
- groupAdjacentSnd :: Eq b => [(a, b)] -> [(NonNull a, b)]
- keyedGroupSort :: Ord.Ord key => (a -> key) -> [a] -> [(key, NonNull a)]
- groupFst :: Ord.Ord a => [(a, b)] -> [(a, NonNull b)]
- groupSnd :: Ord.Ord b => [(a, b)] -> [(NonNull a, b)]
- groupSort :: Ord.Ord key => (a -> key) -> [a] -> [NonNull a]
- groupStableWith :: (a -> a -> Bool) -> [a] -> [NonEmpty a]
- groupStable :: Eq key => (a -> key) -> [a] -> [NonEmpty a]
- keyedGroupStable :: Eq key => (a -> key) -> [a] -> [(key, [a])]
- zipNext :: [a] -> [(a, Maybe.Maybe a)]
- zipNexts :: [a] -> [(a, [a])]
- zipPrev :: [a] -> [(Maybe.Maybe a, a)]
- zipNeighbors :: [a] -> [(Maybe.Maybe a, a, Maybe.Maybe a)]
- zipRemainder :: [a] -> [b] -> ([(a, b)], Either.Either [a] [b])
- zipper :: [a] -> [a] -> [([a], [a])]
- data Paired a b
- pairedSecond :: Paired a b -> Maybe.Maybe b
- pairedFirst :: Paired a b -> Maybe.Maybe a
- partitionPaired :: [Paired a b] -> ([a], [b])
- zipPadded :: [a] -> [b] -> [Paired a b]
- zipPaddedFst :: [a] -> [b] -> [(Maybe.Maybe a, b)]
- zipPaddedSnd :: [a] -> [b] -> [(a, Maybe.Maybe b)]
- diff :: (a -> b -> Bool) -> [a] -> [b] -> [Paired a b]
- diffEither :: (a -> b -> Bool) -> [a] -> [b] -> [Either.Either a b]
- diffIndex :: (a -> b -> Bool) -> [a] -> [b] -> [(Int, Paired a b)]
- diffIndexOn :: Eq k => (a -> k) -> [a] -> [a] -> [(Int, Paired a a)]
- pairSorted :: Ord.Ord k => [(k, a)] -> [(k, b)] -> [(k, Paired a b)]
- pairSortedOn :: Ord.Ord k => (a -> k) -> (b -> k) -> [a] -> [b] -> [Paired a b]
- pairSortedOn1 :: Ord.Ord k => (a -> k) -> [a] -> [a] -> [Paired a a]
- pairOn1 :: Ord.Ord k => (a -> k) -> [a] -> [a] -> [Paired a a]
- partition2 :: (a -> Bool) -> (a -> Bool) -> [a] -> ([a], [a], [a])
- partitionOn :: (a -> Maybe.Maybe b) -> [a] -> ([b], [a])
- chunked :: Int -> [a] -> [[a]]
- rotate :: [[a]] -> [[a]]
- rotate2 :: [[a]] -> [[Maybe.Maybe a]]
- dropBefore :: Ord.Ord key => (a -> key) -> key -> [a] -> [a]
- dropPrefix :: Eq a => [a] -> [a] -> ([a], Bool)
- dropSuffix :: Eq a => [a] -> [a] -> ([a], Bool)
- cartesian :: [[a]] -> [[a]]
- enumerate :: [a] -> [(Int, a)]
- takeEnd :: Int -> [a] -> [a]
- dropEnd :: Int -> [a] -> [a]
- takeWhileEnd :: (a -> Bool) -> [a] -> [a]
- splitWith :: (a -> Maybe.Maybe b) -> [a] -> ([a], [(b, [a])])
- breakWith :: (a -> Maybe.Maybe b) -> [a] -> ([a], Maybe.Maybe (b, [a]))
- mapAccumLM :: Monad m => (state -> x -> m (state, y)) -> state -> [x] -> m (state, [y])
- split :: Eq a => NonNull a -> [a] -> NonNull [a]
- join :: Monoid a => a -> [a] -> a
- splitBefore :: (a -> Bool) -> [a] -> [[a]]
- splitBetween :: (a -> a -> Bool) -> [a] -> [[a]]
- spanWhile :: (a -> Maybe.Maybe b) -> [a] -> ([b], [a])
- dropDups :: Eq k => (a -> k) -> [a] -> [a]
- dropWith :: (a -> a -> Bool) -> [a] -> [a]
- partitionDups :: Ord.Ord k => (a -> k) -> [a] -> ([a], [(a, NonNull a)])
- findDups :: Ord.Ord k => (a -> k) -> [a] -> [(a, NonEmpty a)]
- dropInitialDups :: Eq k => (a -> k) -> [a] -> [a]
- unique :: Ord.Ord a => [a] -> [a]
- uniqueOn :: Ord.Ord k => (a -> k) -> [a] -> [a]
- uniqueSort :: Ord.Ord a => [a] -> [a]
- replace :: Eq a => [a] -> [a] -> [a] -> [a]
- replace1 :: Eq a => a -> [a] -> [a] -> [a]
- count :: Foldable t => (a -> Bool) -> t a -> Int

# Documentation

This is just a list, but is documentation that a return value will never
be null, or an argument should never be null. This is for cases where
`NonEmpty`

is too annoying to work with.

head :: [a] -> Maybe.Maybe a Source #

Total variants of unsafe list operations.

tail :: [a] -> Maybe.Maybe [a] Source #

last :: [a] -> Maybe.Maybe a Source #

unsnoc :: [a] -> Maybe.Maybe ([a], a) Source #

List initial and final element, if any.

# indexing

at :: [a] -> Int -> Maybe.Maybe a Source #

Get `xs !! n`

, but return Nothing if the index is out of range.

insertAt :: Int -> a -> [a] -> [a] Source #

Insert `x`

into `xs`

at index `i`

. If `i`

is out of range, insert at the
beginning or end of the list.

removeAt :: Int -> [a] -> [a] Source #

Remove the element at the given index. Do nothing if the index is out of range.

takeAt :: Int -> [a] -> Maybe.Maybe (a, [a]) Source #

Like `removeAt`

but return the removed element as well.

modifyAt :: Int -> (a -> a) -> [a] -> [a] Source #

Modify element at an index by applying a function to it. If the index is out of range, nothing happens.

findModify :: (a -> Bool) -> (a -> a) -> [a] -> Maybe.Maybe [a] Source #

Find an element, then change it. Return Nothing if the element wasn't found.

updateAt :: a -> Int -> (Maybe.Maybe a -> a) -> [a] -> [a] Source #

Similar to `modifyAt`

, but will insert an element for an out of range
positive index. The list will be extended with `deflt`

, and the modify
function passed a Nothing.

move :: Int -> Int -> [a] -> Maybe.Maybe [a] Source #

Move an element from one index to another, or Nothing if the `from`

index was out of range.

# enumeration

range :: (Num a, Ord.Ord a) => a -> a -> a -> [a] Source #

Enumerate an inclusive range. Uses multiplication instead of successive addition to avoid loss of precision.

Also it doesn't require an Enum instance.

rangeEnd :: (Num a, Ord.Ord a) => a -> a -> a -> [a] Source #

Like `range`

, but always includes the end, even if it doesn't line up on
a step.

# transformation

keyOnJust :: (a -> Maybe.Maybe k) -> [a] -> [(k, a)] Source #

firstLast :: (a -> a) -> (a -> a) -> [a] -> [a] Source #

Apply a function to the first and last elements. Middle elements are unchanged. A null or singleton list is also unchanged.

mapMaybeFst :: (a -> Maybe.Maybe a2) -> [(a, b)] -> [(a2, b)] Source #

Filter on the fst values returning Just.

mapMaybeSnd :: (b -> Maybe.Maybe b2) -> [(a, b)] -> [(a, b2)] Source #

Filter on the snd values returning Just.

mapHeadTail :: (a -> b) -> (a -> b) -> [a] -> [b] Source #

scanlOn :: (accum -> key -> accum) -> (a -> key) -> accum -> [a] -> [(accum, a)] Source #

This is like `scanl`

, but you can scan with a key function. E.g. to
accumulate line lengths: `scanlOn length (+) 0`

.

# min / max

minimumOn :: Ord.Ord k => (a -> k) -> [a] -> Maybe.Maybe a Source #

maximumOn :: Ord.Ord k => (a -> k) -> [a] -> Maybe.Maybe a Source #

minimum :: Ord.Ord a => [a] -> Maybe.Maybe a Source #

maximum :: Ord.Ord a => [a] -> Maybe.Maybe a Source #

# ordered lists

sortOn :: Ord.Ord k => (a -> k) -> [a] -> [a] Source #

Stable sort on a cheap key function. Different from `List.sortOn`

, which
is for an expensive key function.

reverseSortOn :: Ord.Ord b => (a -> b) -> [a] -> [a] Source #

Like `sortOn`

, but sort highest-to-lowest.

merge :: Ord.Ord a => [a] -> [a] -> [a] Source #

Merge sorted lists. If two elements compare equal, the one from the left list comes first.

mergeBy :: (a -> a -> Ord.Ordering) -> [a] -> [a] -> [a] Source #

mergeLists :: Ord.Ord k => (a -> k) -> [[a]] -> [a] Source #

mergeAscLists :: Ord.Ord k => (a -> k) -> [[a]] -> [a] Source #

If the heads of the sublists are also sorted I can be lazy in the list of sublists too. This version is optimized for minimal overlap.

# grouping

## adjacent

groupAdjacent :: Eq key => (a -> key) -> [a] -> [NonNull a] Source #

This is just `List.groupBy`

except with a key function.

keyedGroupAdjacent :: Eq key => (a -> key) -> [a] -> [(key, NonNull a)] Source #

Like `groupAdjacent`

, but include the key.

groupAdjacentFst :: Eq a => [(a, b)] -> [(a, NonNull b)] Source #

groupAdjacentSnd :: Eq b => [(a, b)] -> [(NonNull a, b)] Source #

## sort

:: Ord.Ord key | |

=> (a -> key) | |

-> [a] | |

-> [(key, NonNull a)] | Sorted by key. The NonNull group is in the same order as the input. |

Group the unsorted list into `(key x, xs)`

where all `xs`

compare equal
after `key`

is applied to them.

groupFst :: Ord.Ord a => [(a, b)] -> [(a, NonNull b)] Source #

Similar to `keyedGroupSort`

, but key on the fst element, and strip the
key out of the groups.

groupSnd :: Ord.Ord b => [(a, b)] -> [(NonNull a, b)] Source #

Like `groupFst`

, but group on the snd element.

groupSort :: Ord.Ord key => (a -> key) -> [a] -> [NonNull a] Source #

Like `List.groupBy`

, but the list doesn't need to be sorted, and use a key
function instead of equality. The list is sorted by the key, and the groups
appear in their original order in the input list.

## stable

groupStableWith :: (a -> a -> Bool) -> [a] -> [NonEmpty a] Source #

Group each element with all the other elements that compare equal to it. The heads of the groups appear in their original order.

groupStable :: Eq key => (a -> key) -> [a] -> [NonEmpty a] Source #

`groupStableWith`

but with a key function.

keyedGroupStable :: Eq key => (a -> key) -> [a] -> [(key, [a])] Source #

# zipping

zipNext :: [a] -> [(a, Maybe.Maybe a)] Source #

Pair each element with the following element. The last element is paired
with Nothing. Like `zip xs (drop 1 xs ++ [Nothing])`

but only traverses
`xs`

once.

zipPrev :: [a] -> [(Maybe.Maybe a, a)] Source #

zipNeighbors :: [a] -> [(Maybe.Maybe a, a, Maybe.Maybe a)] Source #

Like `zipNext`

but with both preceding and following elements.

zipRemainder :: [a] -> [b] -> ([(a, b)], Either.Either [a] [b]) Source #

This is like `zip`

, but it returns the remainder of the longer argument
instead of discarding it.

zipper :: [a] -> [a] -> [([a], [a])] Source #

Return the reversed inits paired with the tails. This is like a zipper moving focus along the input list.

# Paired

pairedSecond :: Paired a b -> Maybe.Maybe b Source #

pairedFirst :: Paired a b -> Maybe.Maybe a Source #

partitionPaired :: [Paired a b] -> ([a], [b]) Source #

zipPaddedFst :: [a] -> [b] -> [(Maybe.Maybe a, b)] Source #

Like `zip`

, but the first list is padded with Nothings.

zipPaddedSnd :: [a] -> [b] -> [(a, Maybe.Maybe b)] Source #

Like `zip`

, but the second list is padded with Nothings.

diffEither :: (a -> b -> Bool) -> [a] -> [b] -> [Either.Either a b] Source #

Left if the val was in the left list but not the right, Right for the converse.

diffIndex :: (a -> b -> Bool) -> [a] -> [b] -> [(Int, Paired a b)] Source #

This is like `diff`

, except that the index of each pair in the
*right* list is included. So the index is where you should delete or
add the element to turn as into bs:

`(i, Second b)`

,`i`

is the position of`b`

in`bs`

.`(i, First a)`

,`i`

is where`a`

was deleted from`bs`

.

pairSorted :: Ord.Ord k => [(k, a)] -> [(k, b)] -> [(k, Paired a b)] Source #

Pair up two lists of sorted pairs by their first element.

pairSortedOn :: Ord.Ord k => (a -> k) -> (b -> k) -> [a] -> [b] -> [Paired a b] Source #

Like `pairSorted`

, but use a key function, and omit the extracted key.

pairSortedOn1 :: Ord.Ord k => (a -> k) -> [a] -> [a] -> [Paired a a] Source #

Like `pairSorted`

, but use a key function, and omit the extracted key.

pairOn1 :: Ord.Ord k => (a -> k) -> [a] -> [a] -> [Paired a a] Source #

Like `pairOn`

, but when the lists have the same type.

# partition

partition2 :: (a -> Bool) -> (a -> Bool) -> [a] -> ([a], [a], [a]) Source #

Like `List.partition`

, but partition by two functions consecutively.

partitionOn :: (a -> Maybe.Maybe b) -> [a] -> ([b], [a]) Source #

Partition and transform at the same time.

# sublists

rotate :: [[a]] -> [[a]] Source #

Take a list of rows to a list of columns. This is like a zip except for variable-length lists. Similar to zip, the result is trimmed to the length of the shortest row.

`List.transpose`

is similar, but it skips missing elements, instead of
truncating all to the shortest. Skipping means you lose what column the
element came from.

rotate2 :: [[a]] -> [[Maybe.Maybe a]] Source #

Similar to `rotate`

, except that the result is the length of the longest
row and missing columns are Nothing. Analogous to `zip_padded`

.

# prefix / suffix

dropBefore :: Ord.Ord key => (a -> key) -> key -> [a] -> [a] Source #

Drop until the last element before or equal to the given element.

dropPrefix :: Eq a => [a] -> [a] -> ([a], Bool) Source #

If the list doesn't have the given prefix, return the original list and
False. Otherwise, strip it off and return True. `List.stripPrefix`

is an
alternate version.

dropSuffix :: Eq a => [a] -> [a] -> ([a], Bool) Source #

# permutations

cartesian :: [[a]] -> [[a]] Source #

The cartesian product of a list of lists. E.g.
`[[1, 2], [3, 4]]`

-> `[[1, 3], [1, 4], [2, 3], [2, 4]]`

.

# enumeration

# sublists

takeWhileEnd :: (a -> Bool) -> [a] -> [a] Source #

# split / join

splitWith :: (a -> Maybe.Maybe b) -> [a] -> ([a], [(b, [a])]) Source #

breakWith :: (a -> Maybe.Maybe b) -> [a] -> ([a], Maybe.Maybe (b, [a])) Source #

# transform

mapAccumLM :: Monad m => (state -> x -> m (state, y)) -> state -> [x] -> m (state, [y]) Source #

Like `List.mapAccumL`

, but monadic. Strict in the accumulator.

## split and join

split :: Eq a => NonNull a -> [a] -> NonNull [a] Source #

Split `xs`

on `sep`

, dropping `sep`

from the result.

splitBefore :: (a -> Bool) -> [a] -> [[a]] Source #

Split before places where the function matches.

> splitBefore (==1) [1, 2, 1] [[], [1, 2], [1]]

splitBetween :: (a -> a -> Bool) -> [a] -> [[a]] Source #

Split the list on the points where the given function returns true.

This is similar to `groupBy`

, except this is defined to compare adjacent
elements. `groupBy`

actually compares to the first element of each group.
E.g. you can't group numeric runs with `groupBy (a b -> b > a+1)`

.

# span and break

spanWhile :: (a -> Maybe.Maybe b) -> [a] -> ([b], [a]) Source #

Like `span`

, but it can transform the spanned sublist.

# duplicates

dropDups :: Eq k => (a -> k) -> [a] -> [a] Source #

Drop adjacent elts if they are equal after applying the key function. The first elt is kept.

dropWith :: (a -> a -> Bool) -> [a] -> [a] Source #

Filter out elts when the predicate is true for adjacent elts. The first
elt is kept, and the later ones are dropped. This is like `dropDups`

except it can compare two elements. E.g. `dropWith (>=)`

will ensure the
sequence is increasing.

Sort the input by the key, extract unique values, and also return the duplicates.

findDups :: Ord.Ord k => (a -> k) -> [a] -> [(a, NonEmpty a)] Source #

Find duplicate values. There are always at least 2 of each output.

dropInitialDups :: Eq k => (a -> k) -> [a] -> [a] Source #

Like `dropDups`

, but keep the last adjacent equal elt instead of the
first.

uniqueOn :: Ord.Ord k => (a -> k) -> [a] -> [a] Source #

This is like `dropDups`

, except that it's not limited to just adjacent
elts. The output list is in the same order as the input.

uniqueSort :: Ord.Ord a => [a] -> [a] Source #

Like `unique`

, but sort the list, and should be more efficient.

# replace

replace1 :: Eq a => a -> [a] -> [a] -> [a] Source #

Replace occurrances of an element with zero or more other elements.