| Copyright | (c) Gershom Bazerman 2018 |
|---|---|
| License | BSD-style |
| Maintainer | libraries@haskell.org |
| Portability | portable |
| Safe Haskell | Trustworthy |
| Language | Haskell98 |
Data.Containers.ListUtils
Description
This module provides efficient containers-based functions on the list type.
In the documentation, \(n\) is the number of elements in the list while
\(d\) is the number of distinct elements in the list. \(W\) is the number
of bits in an Int.
Documentation
nubOrd :: Ord a => [a] -> [a] Source #
\( O(n \log d) \). The nubOrd function removes duplicate elements from a
list. In particular, it keeps only the first occurrence of each element. By
using a Set internally it has better asymptotics than the standard
nub function.
Strictness
nubOrd is strict in the elements of the list.
Efficiency note
When applicable, it is almost always better to use nubInt or nubIntOn
instead of this function, although it can be a little worse in certain
pathological cases. For example, to nub a list of characters, use
nubIntOn fromEnum xs
nubOrdOn :: Ord b => (a -> b) -> [a] -> [a] Source #
The nubOrdOn function behaves just like nubOrd except it performs
comparisons not on the original datatype, but a user-specified projection
from that datatype.
Strictness
nubOrdOn is strict in the values of the function applied to the
elements of the list.
nubInt :: [Int] -> [Int] Source #
\( O(n \min(d,W)) \). The nubInt function removes duplicate Int
values from a list. In particular, it keeps only the first occurrence
of each element. By using an IntSet internally, it attains better
asymptotics than the standard nub function.
See also nubIntOn, a more widely applicable generalization.
Strictness
nubInt is strict in the elements of the list.
nubIntOn :: (a -> Int) -> [a] -> [a] Source #
The nubIntOn function behaves just like nubInt except it performs
comparisons not on the original datatype, but a user-specified projection
from that datatype. For example, nubIntOn can be used to
nub characters and typical fixed-with numerical types efficiently.fromEnum
Strictness
nubIntOn is strict in the values of the function applied to the
elements of the list.