Safe Haskell	None
Language	Haskell2010

Mikan.Utils.List

Contents

Variants of list case, cons, head, tail, init, last
Iterators
Lookup and indexing
Traversals
Sublist extraction and partitioning
Prefix and suffix
Chunks
Sorting
List as a set
Zipping
Unzipping
Edit Distance
Reexports

Description

Utility functions for lists.

Synopsis

replicate' :: Int -> a -> [a]
(++!) :: [a] -> [a] -> [a]
snoc :: [a] -> a -> [a]
caseList :: [a] -> b -> (a -> [a] -> b) -> b
caseListM :: Monad m => m [a] -> m b -> (a -> [a] -> m b) -> m b
listCase :: b -> (a -> [a] -> b) -> [a] -> b
headWithDefault :: a -> [a] -> a
tailMaybe :: [a] -> Maybe [a]
tailWithDefault :: [a] -> [a] -> [a]
lastMaybe :: [a] -> Maybe a
lastWithDefault :: a -> [a] -> a
last1 :: a -> [a] -> a
last2 :: [a] -> Maybe (a, a)
last2' :: a -> a -> [a] -> (a, a)
mcons :: Maybe a -> [a] -> [a]
initLast :: [a] -> Maybe ([a], a)
initLast1 :: a -> [a] -> ([a], a)
initLast' :: [a] -> Maybe ([a], a)
initLast1' :: a -> [a] -> ([a], a)
init1 :: a -> [a] -> [a]
initMaybe :: [a] -> Maybe [a]
initWithDefault :: [a] -> [a] -> [a]
asum :: Alternative m => [m a] -> m a
asum1 :: Alternative m => m a -> [m a] -> m a
(!!!) :: [a] -> Int -> Maybe a
(!!) :: HasCallStack => [a] -> Int -> a
indexWithDefault :: a -> [a] -> Int -> a
findWithIndex :: (a -> Bool) -> [a] -> Maybe (a, Int)
findWithIndex' :: (a -> Bool) -> [a] -> b -> (a -> Int -> b) -> b
genericElemIndex :: (Eq a, Integral i) => a -> [a] -> Maybe i
downFrom :: Integral a => a -> [a]
map' :: (a -> b) -> [a] -> [b]
map'' :: (a -> b) -> [a] -> [b]
mapMaybe' :: (a -> Maybe b) -> [a] -> [b]
concatMap' :: (a -> [b]) -> [a] -> [b]
concat' :: [[a]] -> [a]
partition' :: (a -> Bool) -> [a] -> ([a], [a])
partitionEithers' :: [Either a b] -> ([a], [b])
splitExactlyAt :: Integral n => n -> [a] -> Maybe (Prefix a, Suffix a)
splitExactlyAt' :: Int -> [a] -> Maybe (Prefix a, Suffix a)
splitAt' :: Int -> [a] -> ([a], [a])
take' :: Int -> [a] -> [a]
takeWhile' :: (a -> Bool) -> [a] -> [a]
break' :: (a -> Bool) -> [a] -> ([a], [a])
takeExactly :: forall a n. Integral n => a -> n -> [a] -> [a]
dropEnd :: Int -> [a] -> Prefix a
spanEnd :: (a -> Bool) -> [a] -> (Prefix a, Suffix a)
breakAfter1 :: (a -> Bool) -> a -> [a] -> (List1 a, [a])
breakAfter :: (a -> Bool) -> [a] -> ([a], [a])
breakJust :: (a -> Maybe b) -> [a] -> (Prefix a, (b, Suffix a))
takeWhileJust :: (a -> Maybe b) -> [a] -> Prefix b
spanJust :: (a -> Maybe b) -> [a] -> (Prefix b, Suffix a)
partitionMaybe :: (a -> Maybe b) -> [a] -> ([a], [b])
catMaybe' :: [Maybe a] -> [a]
filterAndRest :: (a -> Bool) -> [a] -> ([a], Suffix a)
filter' :: (a -> Bool) -> [a] -> [a]
mapMaybeAndRest :: (a -> Maybe b) -> [a] -> ([b], Suffix a)
dropFrom :: Eq a => List1 a -> [a] -> [a]
holes :: [a] -> [(a, [a])]
replaceAt' :: Int -> a -> [a] -> [a]
type Prefix a = [a]
commonPrefix :: Eq a => [a] -> [a] -> Prefix a
dropCommon :: [a] -> [b] -> (Suffix a, Suffix b)
stripPrefixBy :: (a -> a -> Bool) -> Prefix a -> [a] -> Maybe (Suffix a)
type Suffix a = [a]
commonSuffix :: Eq a => [a] -> [a] -> Suffix a
stripSuffix :: Eq a => Suffix a -> [a] -> Maybe (Prefix a)
stripReversedSuffix :: Eq a => ReversedSuffix a -> [a] -> Maybe (Prefix a)
suffixesSatisfying :: (a -> Bool) -> [a] -> [Bool]
findOverlap :: Eq a => [a] -> [a] -> (Int, Int)
chop :: Int -> [a] -> [[a]]
chopWhen :: (a -> Bool) -> [a] -> [[a]]
sortOnM :: (Monad m, Ord b) => (a -> m b) -> [a] -> m [a]
sorted :: Ord a => [a] -> Bool
allConsecutive :: (a -> a -> Bool) -> [a] -> Bool
mergeStrictlyOrderedBy :: (a -> a -> Bool) -> [a] -> [a] -> Maybe [a]
hasElem :: Ord a => [a] -> a -> Bool
distinct :: Eq a => [a] -> Bool
fastDistinct :: Ord a => [a] -> Bool
duplicates :: Ord a => [a] -> [a]
allDuplicates :: Ord a => [a] -> [a]
nubAndDuplicatesOn :: Ord b => (a -> b) -> [a] -> ([a], [a])
nubOn :: Ord b => (a -> b) -> [a] -> [a]
nubFavouriteOn :: forall a b c. (Ord b, Hashable c) => (a -> b) -> (a -> c) -> [a] -> [a]
uniqOn :: Ord b => (a -> b) -> [a] -> [a]
allEqual :: Eq a => [a] -> Bool
nubM :: Monad m => (a -> a -> m Bool) -> [a] -> m [a]
zip' :: [a] -> [b] -> [(a, b)]
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith'' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWithSameLen :: (a -> b -> c) -> [a] -> [b] -> Maybe [c]
zipWithKeepRest :: (a -> b -> b) -> [a] -> [b] -> [b]
align :: [a] -> [b] -> [These a b]
unzipWith :: (a -> (b, c)) -> [a] -> ([b], [c])
editDistance :: Eq a => [a] -> [a] -> Int
uncons :: [a] -> Maybe (a, [a])

Variants of list case, cons, head, tail, init, last

replicate' :: Int -> a -> [a] Source #

\(\mathcal{O}(n)\). Spine-strict replicate.

(++!) :: [a] -> [a] -> [a] infixr 5 Source #

\(\mathcal{O}(n)\). Spine-strict ++.

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

\(\mathcal{O}(n)\). Append a single element at the end.

This function should be avoided, even if the lists are very short.

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

\(\mathcal{O}(1)\). Case distinction for lists, with list first.

Cf. ifNull.

caseListM :: Monad m => m [a] -> m b -> (a -> [a] -> m b) -> m b Source #

\(\mathcal{O}(1)\). Case distinction for lists, with list first.

Cf. ifNull.

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

\(\mathcal{O}(1)\). Case distinction for lists, with list last.

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

\(\mathcal{O}(1)\). Head function (safe). Returns a default value on empty lists.

Examples

Expand

>>> headWithDefault 42 []
42
>>> headWithDefault 42 [1,2,3]
1

tailMaybe :: [a] -> Maybe [a] Source #

\(\mathcal{O}(1)\). Safe variant of tail.

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

\(\mathcal{O}(1)\). Safe variant of tail. Returns a default list on empty lists.

lastMaybe :: [a] -> Maybe a Source #

\(\mathcal{O}(n)\). Safe variant of last.

This function should be avoided when used inside of recursive functions. If you find yourself reaching for lastMaybe, use a reversed list as the accumulator.

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

\(\mathcal{O}(n)\). Safe variant of last. Returns a default list on empty lists.

This function should be avoided when used inside of recursive functions. If you find yourself reaching for lastWithDefault, use a reversed list as the accumulator.

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

\(\mathcal{O}(n)\). Last element of non-empty list. This function is safe.

Laws

Expand

last1 a as = last (a : as)

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

\(\mathcal{O}(n)\). Last two elements. This function is safe.

last2' :: a -> a -> [a] -> (a, a) Source #

\(\mathcal{O}(n)\). last2' x y zs computes the last two elements of x:y:zs.

mcons :: Maybe a -> [a] -> [a] Source #

\(\mathcal{O}(1)\). Maybe cons.

mcons ma as = maybeToList ma ++ as

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

\(\mathcal{O}(n)\). init and last in one go. This function is safe.

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

\(\mathcal{O}(n)\). init and last of non-empty list, safe.

initLast1 a as = (init (a:as), last (a:as)

initLast' :: [a] -> Maybe ([a], a) Source #

\(\mathcal{O}(n)\). Spine-strict initLast.

initLast1' :: a -> [a] -> ([a], a) Source #

\(\mathcal{O}(n)\). Spine-strict initLast1.

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

\(\mathcal{O}(n)\). init of non-empty list. This function is safe.

init1 a as = init (a:as)

initMaybe :: [a] -> Maybe [a] Source #

\(\mathcal{O}(n)\). init. This function is safe.

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

\(\mathcal{O}(n)\). init. This function is safe.

Iterators

asum :: Alternative m => [m a] -> m a Source #

\(\mathcal{O}(n)\). A version of asum that avoids a final empty. It is right-folding just like asum.

Precondition: the right-unit law holds, i.e. m <|> A.empty = m.

asum1 :: Alternative m => m a -> [m a] -> m a Source #

\(\mathcal{O}(n)\). A right-folding asum for nonempty lists, never producing empty.

Lookup and indexing

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

\(\mathcal{O}(\min(n, i))\). Lookup an element in a list.

(!!) :: HasCallStack => [a] -> Int -> a Source #

A variant of !! that might provide more informative error messages if the index is out of bounds.

Precondition: The index should not be out of bounds.

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

\(\mathcal{O}(\min(n, i))\). Lookup function with default value for index out of range.

findWithIndex :: (a -> Bool) -> [a] -> Maybe (a, Int) Source #

\(\mathcal{O}(n)\). Find the first element satisfying a predicate and return it with its index.

findWithIndex' :: (a -> Bool) -> [a] -> b -> (a -> Int -> b) -> b Source #

\(\mathcal{O}(n)\). Variant of findWithIndex that returns a CPS'd Maybe result for more reliable inlining.

genericElemIndex :: (Eq a, Integral i) => a -> [a] -> Maybe i Source #

\(\mathcal{O}(n)\). A generalised variant of elemIndex.

downFrom :: Integral a => a -> [a] Source #

\(\mathcal{O}(n)\). Return a descending list of numbers. This function is spine-strict.

Laws

Expand

downFrom n = [n-1,..1,0]

Traversals

map' :: (a -> b) -> [a] -> [b] Source #

\(\mathcal{O}(n)\). Strict map.

map'' :: (a -> b) -> [a] -> [b] Source #

\(\mathcal{O}(n)\). Spine-strict map.

mapMaybe' :: (a -> Maybe b) -> [a] -> [b] Source #

\(\mathcal{O}(n)\). Strict mapMaybe.

concatMap' :: (a -> [b]) -> [a] -> [b] Source #

\(\mathcal{O}(n)\). Strict concatMap

concat' :: [[a]] -> [a] Source #

\(\mathcal{O}(n)\). Strict concat.

Sublist extraction and partitioning

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

\(\mathcal{O}(n)\). Strict partition.

partitionEithers' :: [Either a b] -> ([a], [b]) Source #

\(\mathcal{O}(n)\). Strict partitionEithers.

splitExactlyAt :: Integral n => n -> [a] -> Maybe (Prefix a, Suffix a) Source #

\(\mathcal{O}(n)\). Split a list at some index. If the index is out of bounds, return Nothing.

Laws

Expand

splitExactlyAt n xs = Just (ys, zs) iff xs = ys ++ zs and genericLength ys = n.

splitExactlyAt' :: Int -> [a] -> Maybe (Prefix a, Suffix a) Source #

\(\mathcal{O}(n)\). Spine-strict splitExactlyAt.

splitAt' :: Int -> [a] -> ([a], [a]) Source #

\(\mathcal{O}(n)\). Spine-strict splitAt.

take' :: Int -> [a] -> [a] Source #

\(\mathcal{O}(n)\). Spine-strict take.

takeWhile' :: (a -> Bool) -> [a] -> [a] Source #

\(\mathcal{O}(n)\). Strict takeWhile.

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

\(\mathcal{O}(n)\). Strict break.

takeExactly :: forall a n. Integral n => a -> n -> [a] -> [a] Source #

\(\mathcal{O}(n)\). takeExactly x n xs takes n elements from xs, padding with x if we reach the end of the list.

Laws

Expand

takeExactly x n xs == take n (xs ++ repeat x)

dropEnd :: Int -> [a] -> Prefix a Source #

\(\mathcal{O}(n)\). Drop from the end of a list. Forces the whole list even for n==0.

Laws

Expand

dropEnd n = reverse . drop n . reverse

spanEnd :: (a -> Bool) -> [a] -> (Prefix a, Suffix a) Source #

\(\mathcal{O}(n)\). Split off the largest suffix whose elements satisfy a predicate.

Laws

Expand

all p ys && maybe True (not . p) (lastMaybe xs) ==> spanEnd p (xs, zs) = (xs, ys)

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

\(\mathcal{O}(n)\). Breaks a non-empty list just after an element satisfying the predicate is found.

Examples

Expand

>>> breakAfter1 even 1 [3,5,2,4,7,8]
(1 :| [3,5,2],[4,7,8])

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

Breaks a list just after an element satisfying the predicate is found.

Examples

Expand

>>> breakAfter even [1,3,5,2,4,7,8]
([1,3,5,2],[4,7,8])

breakJust :: (a -> Maybe b) -> [a] -> (Prefix a, (b, Suffix a)) Source #

Break a list when the given predicate returns Just b and place b as pivot between the prefix (where the predicate returns Nothing) and the suffix.

Crashes when the predicate holds nowhere.

takeWhileJust :: (a -> Maybe b) -> [a] -> Prefix b Source #

\(\mathcal{O}(n)\). A generalized version of takeWhile. (Cf. mapMaybe vs. filter).

Laws

Expand

takeWhileJust f = fst . spanJust f

spanJust :: (a -> Maybe b) -> [a] -> (Prefix b, Suffix a) Source #

\(\mathcal{O}(n)\). A generalized version of span.

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

\(\mathcal{O}(n)\). Partition a list into Nothings and Justs.

Laws

Expand

partitionMaybe f = partitionEithers . map (\ a -> maybe (Left a) Right (f a))
mapMaybe f = snd . partitionMaybe f

catMaybe' :: [Maybe a] -> [a] Source #

\(\mathcal{O}(n)\). Spine-strict catMaybes.

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

\(\mathcal{O}(n)\). Like filter, but additionally return the last partition of the list where the predicate is False everywhere.

filter' :: (a -> Bool) -> [a] -> [a] Source #

\(\mathcal{O}(n)\). Strict filter.

mapMaybeAndRest :: (a -> Maybe b) -> [a] -> ([b], Suffix a) Source #

\(\mathcal{O}(n)\). Like mapMaybe, but additionally return the last partition of the list where the function always returns Nothing.

dropFrom :: Eq a => List1 a -> [a] -> [a] Source #

dropFrom marker xs drops everything from xs starting with (and including) marker.

If the marker does not appear, the string is returned unchanged.

The following two properties hold provided marker has no overlap with xs:

  dropFrom marker (xs ++ marker ++ ys) == xs
  dropFrom marker xs == xs

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

\(\mathcal{O}(n^2)\). All ways of removing one element from a list.

replaceAt' :: Int -> a -> [a] -> [a] Source #

\(\mathcal{O}(n)\). Replace the element at the given index with the given value.

Spine-strict.

Prefix and suffix

Prefix

type Prefix a Source #

Arguments

= [a]

The list before the split point.

commonPrefix :: Eq a => [a] -> [a] -> Prefix a Source #

\(\mathcal{O}(\min(m, n))\). Compute the common prefix of two lists.

dropCommon :: [a] -> [b] -> (Suffix a, Suffix b) Source #

\(\mathcal{O}(\min(m, n))\). Drops from both lists simultaneously until one list is empty.

stripPrefixBy :: (a -> a -> Bool) -> Prefix a -> [a] -> Maybe (Suffix a) Source #

\(\mathcal{O}(n)\). Check if a list has a given prefix. If so, return the list minus the prefix.

Suffix

type Suffix a Source #

Arguments

= [a]

The list after the split point.

commonSuffix :: Eq a => [a] -> [a] -> Suffix a Source #

\(\mathcal{O}(m + n)\). Compute the common suffix of two lists.

stripSuffix :: Eq a => Suffix a -> [a] -> Maybe (Prefix a) Source #

\(\mathcal{O}(n)\). stripSuffix suf xs = Just pre iff xs = pre ++ suf.

Laws

Expand

stripSuffix suf (pre ++ sufh) = Just pre

stripReversedSuffix :: Eq a => ReversedSuffix a -> [a] -> Maybe (Prefix a) Source #

\(\mathcal{O}(n)\).

Laws

Expand

stripReversedSuffix suf (pre ++ reverse suf) = Just pre

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

Returns a list with one boolean for each non-empty suffix of the list, starting with the longest suffix (the entire list). Each boolean is True exactly when every element in the corresponding suffix satisfies the predicate.

Examples

Expand

>>> suffixesSatisfying isLower "AbCde"
[False, False, False, True, True]

Laws

Expand

For total predicates p and finite and total lists xs the following holds:

suffixesSatisfying p xs = map (all p) (init (tails xs))

Finding overlap

findOverlap :: Eq a => [a] -> [a] -> (Int, Int) Source #

\(\mathcal{O}(\min(m, n)^2)\). Find the longest suffix of the first string xs that is a prefix of the second string ys. So, basically, find the overlap where the strings can be glued together. Returns the index where the overlap starts and the length of the overlap. The length of the overlap plus the index is the length of the first string. Note that in the worst case, the empty overlap (length xs,0) is returned.

There might be asymptotically better implementations following Knuth-Morris-Pratt or Boyer-Moore, but for rather short lists this is good enough.

Chunks

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

\(\mathcal{O}(n)\). Chop up a list in chunks of a given length.

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

\(\mathcal{O}(n)\). Chop a list at the positions when the predicate holds. Contrary to wordsBy, consecutive separator elements will result in an empty segment in the result.

Laws

Expand

intercalate [x] (chopWhen (== x) xs) == xs

Sorting

sortOnM :: (Monad m, Ord b) => (a -> m b) -> [a] -> m [a] Source #

\(\mathcal{O}(n \log n)\). Monadic version of sortOn.

The effect is executed exactly once for each list element.

sorted :: Ord a => [a] -> Bool Source #

\(\mathcal{O}(n)\). Check whether a list is sorted.

Assumes that the Ord instance implements a partial order.

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

\(\mathcal{O}(n)\). Check whether all consecutive elements of a list satisfy the given relation.

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

\(\mathcal{O}(\min(m, n))\). Merge two lists using a comparison function.

If any of the elements of the list are incomparable, returns Nothing. Otherwise, returns a Just containing a sorted list.

List as a set

hasElem :: Ord a => [a] -> a -> Bool Source #

Check membership for the same list often. Use partially applied to create membership predicate hasElem xs :: a -> Bool.

First time: \(\mathcal{O}(n \log n)\) in the worst case.
Subsequently: \(\mathcal{O}(\log n)\).

Laws

Expand

hasElem xs == (`elem` xs)

distinct :: Eq a => [a] -> Bool Source #

\(\mathcal{O}(n^2)\). Check whether all elements in a list are distinct from each other. Assumes that the Eq instance stands for an equivalence relation.

fastDistinct :: Ord a => [a] -> Bool Source #

\(\mathcal{O}(n \log n)\). An optimised version of distinct.

Precondition: The list's length must fit in an Int.

duplicates :: Ord a => [a] -> [a] Source #

\(\mathcal{O}(n \log n)\). Returns an (arbitrary) representative for each list element that occurs more than once.

duplicates is strict in the spine of the list.

Examples

Expand

>>> duplicates "abcbcdbb"
"bc"

>>> duplicates [1,0,2,2,2,2,1,9]
[2,2,2,1]

allDuplicates :: Ord a => [a] -> [a] Source #

\(\mathcal{O}(n \log n)\) Remove the first representative for each list element.

The elements of the list are returned in the same order.

allDuplicates is strict in the spine of the list.

Examples

Expand

>>> duplicates [1,2,2,0,3,3,3,3,2,1,9]
[2,3,3,3,2,1]

nubAndDuplicatesOn :: Ord b => (a -> b) -> [a] -> ([a], [a]) Source #

\(\mathcal{O}(n \log n)\). Partition a list into first and later occurrences of elements (modulo some quotient given by a representation function).

Laws

Expand

nubAndDuplicatesOn f xs = (ys, xs List.\\ ys)
  where ys = nubOn f xs

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

\(\mathcal{O}(n \log n)\). Efficient variant of nubBy for lists, using a set to store already seen elements.

Laws

Expand

nubOn f xs == nubBy ((==) `on` f) xs.

nubFavouriteOn Source #

Arguments

:: forall a b c. (Ord b, Hashable c)
=> (a -> b)	The values returned by this function are used to determine which element from a group of equal elements that is returned: the smallest one is chosen (and if two elements are equally small, then the first one is chosen).
-> (a -> c)	Two elements are treated as equal if this function returns the same value for both elements.
-> [a]
-> [a]

A variant of nubOn that is parametrised by a function that is used to select which element from a group of equal elements that is returned. The returned elements keep the order that they had in the input list.

Precondition: The length of the input list must be at most maxBound :: Int.

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

\(\mathcal{O}(n \log n)\). Efficient variant of nubBy for finite lists.

If there are several elements with the same f-representative, the first of these is kept.

Laws

Expand

uniqOn f == 'List.sortBy' (compare `'on'` f) . 'List.nubBy' ((==) `'on'` f)

allEqual :: Eq a => [a] -> Bool Source #

\(\mathcal{O}(n)\). Checks if all the elements in the list are equal. Assumes that the Eq instance stands for an equivalence relation.

nubM :: Monad m => (a -> a -> m Bool) -> [a] -> m [a] Source #

\(\mathcal{O}(n^2)\). Non-efficient, monadic nub.

Zipping

zip' :: [a] -> [b] -> [(a, b)] Source #

\(\mathcal{O}(\min(m, n))\). Spine-strict zipping.

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c] Source #

\(\mathcal{O}(\min(m, n))\). Strict zipWith.

zipWith'' :: (a -> b -> c) -> [a] -> [b] -> [c] Source #

\(\mathcal{O}(\min(m, n))\). Spine-strict zipWith.

zipWithSameLen :: (a -> b -> c) -> [a] -> [b] -> Maybe [c] Source #

\(\mathcal{O}(\min(m, n))\). Requires both lists to have the same length. Otherwise, Nothing is returned.

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

\(\mathcal{O}(\min(m, n))\). Like zipWith but keep the rest of the second list as-is (in case the second list is longer).

Laws

Expand

zipWithKeepRest f as bs == zipWith f as bs ++ drop (length as) bs

align :: [a] -> [b] -> [These a b] Source #

\(\mathcal{O}(\max(m, n))\). Analogous to zip, combines two lists by taking the union using a strict These.

Unzipping

unzipWith :: (a -> (b, c)) -> [a] -> ([b], [c]) Source #

Split a list into a pair of lists.

Edit Distance

editDistance :: Eq a => [a] -> [a] -> Int Source #

\(\mathcal{O}(mn)\). Find the edit distance between two lists.

Reexports

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

\(\mathcal{O}(1)\). 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.

Examples

Expand

>>> uncons []
Nothing

>>> uncons [1]
Just (1,[])

>>> uncons [1, 2, 3]
Just (1,[2,3])

Since: base-4.8.0.0