containers-0.6.2.1: Assorted concrete container types

Data.Containers.ListUtils

Description

This module provides efficient containers-based functions on the list type.

In the documentation, $$n$$ is the number of elements in the list while $$d$$ is the number of distinct elements in the list. $$W$$ is the number of bits in an Int.

Synopsis

# Documentation

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

$$O(n \log d)$$. 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

nubOrdOn :: Ord b => (a -> b) -> [a] -> [a] Source #

The nubOrdOn function behaves just like nubOrd except it performs comparisons not on the original datatype, but a user-specified projection from that datatype.

#### Strictness

nubOrdOn is strict in the values of the function applied to the elements of the list.

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

$$O(n \min(d,W))$$. The nubInt function removes duplicate Int values from a list. In particular, it keeps only the first occurrence of each element. By using an IntSet internally, it attains better asymptotics than the standard nub function.

See also nubIntOn, a more widely applicable generalization.

#### Strictness

nubInt is strict in the elements of the list.

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

The nubIntOn function behaves just like nubInt except it performs comparisons not on the original datatype, but a user-specified projection from that datatype. For example, nubIntOn fromEnum can be used to nub characters and typical fixed-with numerical types efficiently.

#### Strictness

nubIntOn is strict in the values of the function applied to the elements of the list.