Copyright	(c) 2016 Stephen Diehl (c) 2016-2018 Serokell (c) 2018-2021 Kowainik
License	MIT
Maintainer	Kowainik <xrom.xkov@gmail.com>
Stability	Stable
Portability	Portable
Safe Haskell	Safe
Language	Haskell2010

Relude.Nub

Description

Functions to remove duplicates from a list.

Performance

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:

Lists which consist of many different elements
Lists which consist of many same elements

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.

Synopsis

hashNub :: forall a. (Eq a, Hashable a) => [a] -> [a]
ordNub :: forall a. Ord a => [a] -> [a]
ordNubOn :: forall b a. Ord b => (a -> b) -> [a] -> [a]
intNub :: [Int] -> [Int]
intNubOn :: (a -> Int) -> [a] -> [a]
sortNub :: Ord a => [a] -> [a]
unstableNub :: (Eq a, Hashable a) => [a] -> [a]

Documentation

hashNub :: forall a. (Eq a, Hashable a) => [a] -> [a] Source #

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

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

ordNub :: forall a. Ord a => [a] -> [a] Source #

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

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

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

ordNubOn :: forall b a. Ord b => (a -> b) -> [a] -> [a] Source #

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

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

Since: 1.0.0.0

intNub :: [Int] -> [Int] Source #

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

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

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

Since: 1.0.0.0

intNubOn :: (a -> Int) -> [a] -> [a] Source #

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

>>> intNubOn fromEnum "ababbbcdaffee"
"abcdfe"

Since: 1.0.0.0

sortNub :: Ord a => [a] -> [a] Source #

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

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

unstableNub :: (Eq a, Hashable a) => [a] -> [a] Source #

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

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