relude-1.0.0.0: Safe, performant, user-friendly and lightweight Haskell Standard Library
Copyright(c) 2016 Stephen Diehl
(c) 2016-2018 Serokell
(c) 2018-2021 Kowainik
LicenseMIT
MaintainerKowainik <xrom.xkov@gmail.com>
StabilityStable
PortabilityPortable
Safe HaskellSafe
LanguageHaskell2010

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

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]