Copyright | (c) Gershom Bazerman 2018 |
---|---|
License | BSD-style |
Maintainer | libraries@haskell.org |
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
.
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.