:: Ord a => [a] -> [a] -package:numeric-prelude -package:universum -package:base -package:express
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
Like
nub, but has
O(n log n) complexity instead of
O(n^2). Code for
ordNub and
listUnion taken
from Niklas Hambüchen's
ordnub package.
A right-biased version of
ordNub.
Example:
>>> ordNub [1,2,1] :: [Int]
[1,2]
>>> ordNubRight [1,2,1] :: [Int]
[2,1]
Remove duplicates but keep elements in order. O(n * log n)
O(n log n). The
nubOrd function removes duplicate
elements from a list. In particular, it keeps only the first
occurrence of each element. Unlike the standard
nub operator,
this version requires an
Ord instance and consequently runs
asymptotically faster.
nubOrd "this is a test" == "this ae"
nubOrd (take 4 ("this" ++ undefined)) == "this"
\xs -> nubOrd xs == nub xs
O(n log n). The
nubSort function sorts and removes
duplicate elements from a list. In particular, it keeps only the first
occurrence of each element.
nubSort "this is a test" == " aehist"
\xs -> nubSort xs == nub (sort xs)
The
sort function implements a stable sorting algorithm. It is
a special case of
sortBy, which allows the programmer to supply
their own comparison function.
Elements are arranged from lowest to highest, keeping duplicates in
the order they appeared in the input.
>>> sort [1,6,4,3,2,5]
[1,2,3,4,5,6]
Removes duplicate elements from a list, keeping only the first
occurance of the element.
Like
nub but runs in <math> time and requires
Ord.
>>> ordNub [3, 3, 3, 2, 2, -1, 1]
[3,2,-1,1]
Like
ordNub runs in <math> but also sorts a list.
>>> sortNub [3, 3, 3, 2, 2, -1, 1]
[-1,1,2,3]
On ordered lists,
nub is equivalent to
nub, except that
it runs in linear time instead of quadratic. On unordered lists it
also removes elements that are smaller than any preceding element.
nub [1,1,1,2,2] == [1,2]
nub [2,0,1,3,3] == [2,3]
nub = nubBy (<)
The
sort function implements a stable sorting algorithm. It is
a special case of
sortBy, which allows the programmer to supply
their own comparison function.
The
nubSort function is equivalent to
nub .
sort, except that duplicates are removed as it sorts. It
is essentially the same implementation as
Data.List.sort,
with
merge replaced by
union. Thus the performance of
nubSort should better than or nearly equal to
sort
alone. It is faster than both
sort and
nub .
sort when the input contains significant quantities of
duplicated elements.
O(n log n). Perform a heap sort
Reduce a list of statuses to just one of each status, and if all
statuses are present return the empty list.
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.
Sort a list and remove duplicates. Like
deleteAllDuplicates,
but trades off laziness and stability for efficiency.
Sort the list, discarding duplicates.
Get all elements with more than one occurrence.