Copyright	(c) 2016 Stephen Diehl (c) 2016-2018 Serokell (c) 2018-2019 Kowainik
License	MIT
Maintainer	Kowainik <xrom.xkov@gmail.com>
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 recomendations for usage of particular functions based on benchmarking resutls.

hashNub is faster than ordNub when there're not so many different values in the list.
hashNub is the fastest with Text.
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 :: (Eq a, Hashable a) => [a] -> [a]
ordNub :: Ord a => [a] -> [a]
sortNub :: Ord a => [a] -> [a]
unstableNub :: (Eq a, Hashable a) => [a] -> [a]

Documentation

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

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 :: Ord a => [a] -> [a] #

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]

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

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] #

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]