Copyright | (c) Gershom Bazerman 2018 |
---|---|
License | BSD-style |
Maintainer | [email protected] |
Portability | portable |
Safe Haskell | Trustworthy |
Language | Haskell98 |
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
.
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.
nubOrd
is strict in the elements of the list.
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.
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.
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 fromEnum
can be used to nub characters and typical fixed-with numerical types efficiently.
nubIntOn
is strict in the values of the function applied to the elements of the list.
© The University of Glasgow and others
Licensed under a BSD-style license (see top of the page).
https://downloads.haskell.org/~ghc/8.8.3/docs/html/libraries/containers-0.6.2.1/Data-Containers-ListUtils.html