Modulerelude-1.2.0.0Haskell2010

Relude.Nub

SPDX-License-Identifier : MIT Maintainer : Kowainik xrom.xkov@gmail.com Stability : Stable Portability : Portable

Functions to remove duplicates from a list.

To check the performance there was done a bunch of benchmarks. Benchmarks were made on lists of Ints and Texts. There were two types of list to use:

Here are some recommendations for usage of particular functions based on benchmarking results.

hashNub is faster than ordNub when there're not so many different values in the list.
hashNub is the fastest with Text.
intNub is faster when you work with lists of Ints.
intNubOn is fast with the lists of type that can have fixed number representations.
sortNub has better performance than ordNub but should be used when sorting is also needed.
unstableNub has better performance than hashNub but doesn't save the original order.

valuehashNub :: Hashable a => [a] -> [a]

Like Prelude.nub but runs in O(n \log_{16} n) time and requires Hashable.

Example1 expression

>>> hashNub [3, 3, 3, 2, 2, -1, 1][3,2,-1,1]

valueordNub :: Ord a => [a] -> [a]

Removes duplicate elements from a list, keeping only the first occurance of the element.

Like Prelude.nub but runs in O(n \log n) time and requires Ord.

Example1 expression

>>> ordNub [3, 3, 3, 2, 2, -1, 1][3,2,-1,1]

valueordNubOn :: Ord b => (a -> b) -> [a] -> [a]

Similar to ordNub but performs nub through the mapped list on the given function.

Example1 expression

>>> ordNubOn (`div` 10) [3, 3, 3, 13, 2, 22, -1, 1, 66][3,13,22,-1,66]

valueintNub :: [Int] -> [Int]

Removes duplicate elements from a list, keeping only the first occurance of the element.

Like Prelude.nub but runs in O (n \min (n, int\_bits )) time and requires Ord.

Example1 expression

>>> intNub [3, 3, 3, 2, 2, -1, 1][3,2,-1,1]

valueintNubOn :: (a -> Int) -> [a] -> [a]

Similar to intNub but works on lists of any types by performing "nubbing" through Ints.

Example1 expression

>>> intNubOn fromEnum "ababbbcdaffee""abcdfe"

valuesortNub :: Ord a => [a] -> [a]

Like ordNub runs in O(n \log n) but also sorts a list.

Example1 expression

>>> sortNub [3, 3, 3, 2, 2, -1, 1][-1,1,2,3]

valueunstableNub :: Hashable a => [a] -> [a]

Like hashNub runs in O(n \log_{16} n) but has better performance; it doesn't save the order.

Example1 expression

>>> unstableNub [3, 3, 3, 2, 2, -1, 1][1,2,3,-1]