Append a single element at the end. Time: O(length); use only on small lists.

Case distinction for lists, with list first. O(1).

Cf. ifNull.

Case distinction for lists, with list first. O(1).

Cf. ifNull.

Case distinction for lists, with list last. O(1).

Head function (safe). Returns a default value on empty lists. O(1).

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

Tail function (safe). O(1).

Tail function (safe). Returns a default list on empty lists. O(1).

Last element (safe). O(n).

Last two elements (safe). O(n).

Opposite of cons (:), safe. O(1).

Maybe cons. O(1). mcons ma as = maybeToList ma ++ as

init and last in one go, safe. O(n).

init, safe. O(n).

Lookup function (partially safe). O(min n index).

Lookup function with default value for index out of range. O(min n index).

The name is chosen akin to genericIndex.

Find an element satisfying a predicate and return it with its index. O(n) in the worst case, e.g. findWithIndex f xs = Nothing.

TODO: more efficient implementation!?

A generalised variant of elemIndex. O(n).

downFrom n = [n-1,..1,0]. O(n).

Update the first element of a list, if it exists. O(1).

Update the last element of a list, if it exists. O(n).

Update nth element of a list, if it exists. O(min index n).

Precondition: the index is >= 0.

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

Drop from the end of a list. O(length).

dropEnd n = reverse . drop n . reverse

Forces the whole list even for n==0.

Split off the largest suffix whose elements satisfy a predicate. O(n).

spanEnd p xs = (ys, zs) where xs = ys ++ zs and all p zs and maybe True (not . p) (lastMaybe yz).

A generalized version of takeWhile. (Cf. mapMaybe vs. filter). @O(length . takeWhileJust f).

takeWhileJust f = fst . spanJust f.

A generalized version of span. O(length . fst . spanJust f).

Partition a list into Nothings and Justs. O(n).

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

Note: mapMaybe f = snd . partitionMaybe f.

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

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

Sublist relation.

All ways of removing one element from a list. O(n²).

Compute the common prefix of two lists. O(min n m).

Drops from both lists simultaneously until one list is empty. O(min n m).

Check if a list has a given prefix. If so, return the list minus the prefix. O(length prefix).

Compute the common suffix of two lists. O(n + m).

stripSuffix suf xs = Just pre iff xs = pre ++ suf. O(n).

stripReversedSuffix rsuf xs = Just pre iff xs = pre ++ reverse suf. O(n).

Internal state for stripping suffix.

groupOn f = groupBy ((==) `on` f) . sortBy (compare `on` f). O(n log n).

A variant of groupBy which applies the predicate to consecutive pairs. O(n).

Split a list into sublists. Generalisation of the prelude function words. O(n).

words xs == wordsBy isSpace xs

Chop up a list in chunks of a given length. 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. O(n).

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

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

• First time: O(n log n) in the worst case.
• Subsequently: O(log n).

Specification: hasElem xs == (elem xs).

Check whether a list is sorted. O(n).

Assumes that the Ord instance implements a partial order.

Check whether all elements in a list are distinct from each other. Assumes that the Eq instance stands for an equivalence relation.

O(n²) in the worst case distinct xs == True.

An optimised version of distinct. O(n log n).

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

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

Remove the first representative for each list element. Thus, returns all duplicate copies. O(n log n).

allDuplicates xs == sort $ xs \ nub xs.

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

Specification:

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

Efficient variant of nubBy for finite lists. O(n log n).

Specification: For each list xs there is a list ys which is a permutation of xs such that

uniqOn f xs == 'nubBy' ((==) `'on'` f) ys.

Furthermore:

List.sortBy (compare `on` f) (uniqOn f xs) == uniqOn f xs
uniqOn id == Set.toAscList . Set.fromList

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

Requires both lists to have the same length. O(n).

Otherwise, Nothing is returned.

Like zipWith but keep the rest of the second list as-is (in case the second list is longer). O(n).

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

Implemented using tree recursion, don't run me at home! O(3^(min n m)).

Implemented using dynamic programming and Data.Array. O(n*m).