Data.Sequence.Internal.Sorting

Safe Haskell	Safe-Inferred
Language	Haskell98

Sort Functions

sort :: Ord a => Seq a -> Seq a Source

\( O(n \log n) \). sort sorts the specified Seq by the natural ordering of its elements. The sort is stable. If stability is not required, unstableSort can be slightly faster.

Since: containers-0.3.0

sortBy :: (a -> a -> Ordering) -> Seq a -> Seq a Source

\( O(n \log n) \). sortBy sorts the specified Seq according to the specified comparator. The sort is stable. If stability is not required, unstableSortBy can be slightly faster.

Since: containers-0.3.0

sortOn :: Ord b => (a -> b) -> Seq a -> Seq a Source

\( O(n \log n) \). sortOn sorts the specified Seq by comparing the results of a key function applied to each element. sortOn f is equivalent to sortBy (compare `on` f), but has the performance advantage of only evaluating f once for each element in the input list. This is called the decorate-sort-undecorate paradigm, or Schwartzian transform.

An example of using sortOn might be to sort a Seq of strings according to their length:

sortOn length (fromList ["alligator", "monkey", "zebra"]) == fromList ["zebra", "monkey", "alligator"]

If, instead, sortBy had been used, length would be evaluated on every comparison, giving \( O(n \log n) \) evaluations, rather than \( O(n) \).

If f is very cheap (for example a record selector, or fst), sortBy (compare `on` f) will be faster than sortOn f.

Since: containers-0.5.11

unstableSort :: Ord a => Seq a -> Seq a Source

\( O(n \log n) \). unstableSort sorts the specified Seq by the natural ordering of its elements, but the sort is not stable. This algorithm is frequently faster and uses less memory than sort.

unstableSortBy :: (a -> a -> Ordering) -> Seq a -> Seq a Source

\( O(n \log n) \). A generalization of unstableSort, unstableSortBy takes an arbitrary comparator and sorts the specified sequence. The sort is not stable. This algorithm is frequently faster and uses less memory than sortBy.

Since: containers-0.3.0

unstableSortOn :: Ord b => (a -> b) -> Seq a -> Seq a Source

\( O(n \log n) \). unstableSortOn sorts the specified Seq by comparing the results of a key function applied to each element. unstableSortOn f is equivalent to unstableSortBy (compare `on` f), but has the performance advantage of only evaluating f once for each element in the input list. This is called the decorate-sort-undecorate paradigm, or Schwartzian transform.

An example of using unstableSortOn might be to sort a Seq of strings according to their length:

unstableSortOn length (fromList ["alligator", "monkey", "zebra"]) == fromList ["zebra", "monkey", "alligator"]

If, instead, unstableSortBy had been used, length would be evaluated on every comparison, giving \( O(n \log n) \) evaluations, rather than \( O(n) \).

If f is very cheap (for example a record selector, or fst), unstableSortBy (compare `on` f) will be faster than unstableSortOn f.

Since: containers-0.5.11

Heaps

The following are definitions for various specialized pairing heaps.

All of the heaps are defined to be non-empty, which speeds up the merge functions.

data Queue e Source

A simple pairing heap.

data QList e Source

data IndexedQueue e Source

A pairing heap tagged with the original position of elements, to allow for stable sorting.

data IQList e Source

data TaggedQueue a b Source

A pairing heap tagged with some key for sorting elements, for use in unstableSortOn.

data TQList a b Source

data IndexedTaggedQueue e a Source

A pairing heap tagged with both a key and the original position of its elements, for use in sortOn.

data ITQList e a Source

Merges

The following are definitions for "merge" for each of the heaps above. Each takes a comparison function which is used to order the elements.

mergeQ :: (a -> a -> Ordering) -> Queue a -> Queue a -> Queue a Source

mergeQ merges two Queues.

mergeIQ :: (a -> a -> Ordering) -> IndexedQueue a -> IndexedQueue a -> IndexedQueue a Source

mergeIQ merges two IndexedQueues, taking into account the original position of the elements.

mergeTQ :: (a -> a -> Ordering) -> TaggedQueue a b -> TaggedQueue a b -> TaggedQueue a b Source

mergeTQ merges two TaggedQueues, based on the tag value.

mergeITQ :: (a -> a -> Ordering) -> IndexedTaggedQueue a b -> IndexedTaggedQueue a b -> IndexedTaggedQueue a b Source

mergeITQ merges two IndexedTaggedQueues, based on the tag value, taking into account the original position of the elements.

popMin

The following are definitions for popMin, a function which constructs a stateful action which pops the smallest element from the queue, where "smallest" is according to the supplied comparison function.

All of the functions fail on an empty queue.

Each of these functions is structured something like this:

popMinQ cmp (Q x ts) = (mergeQs ts, x)

The reason the call to mergeQs is lazy is that it will be bottom for the last element in the queue, preventing us from evaluating the fully sorted sequence.

popMinQ :: (e -> e -> Ordering) -> Queue e -> (Queue e, e) Source

Pop the smallest element from the queue, using the supplied comparator.

popMinIQ :: (e -> e -> Ordering) -> IndexedQueue e -> (IndexedQueue e, e) Source

Pop the smallest element from the queue, using the supplied comparator, deferring to the item's original position when the comparator returns EQ.

popMinTQ :: (a -> a -> Ordering) -> TaggedQueue a b -> (TaggedQueue a b, b) Source

Pop the smallest element from the queue, using the supplied comparator on the tag.

popMinITQ :: (e -> e -> Ordering) -> IndexedTaggedQueue e b -> (IndexedTaggedQueue e b, b) Source

Pop the smallest element from the queue, using the supplied comparator on the tag, deferring to the item's original position when the comparator returns EQ.

Building

The following are definitions for functions to build queues, given a comparison function.

buildQ :: (b -> b -> Ordering) -> (a -> Queue b) -> FingerTree a -> Maybe (Queue b) Source

buildIQ :: (b -> b -> Ordering) -> (Int -> Elem y -> IndexedQueue b) -> Int -> FingerTree (Elem y) -> Maybe (IndexedQueue b) Source

buildTQ :: (b -> b -> Ordering) -> (a -> TaggedQueue b c) -> FingerTree a -> Maybe (TaggedQueue b c) Source

buildITQ :: (b -> b -> Ordering) -> (Int -> Elem y -> IndexedTaggedQueue b c) -> Int -> FingerTree (Elem y) -> Maybe (IndexedTaggedQueue b c) Source

Special folds

A big part of what makes the heaps fast is that they're non empty, so the merge function can avoid an extra case match. To take advantage of this, though, we need specialized versions of foldMap and foldMapWithIndex, which can alternate between calling the faster semigroup-like merge when folding over non empty structures (like Node and Digit), and the Option-like mappend, when folding over structures which can be empty (like FingerTree).

foldToMaybeTree :: (b -> b -> b) -> (a -> b) -> FingerTree a -> Maybe b Source

A foldMap-like function, specialized to the Option monoid, which takes advantage of the internal structure of Seq to avoid wrapping in Maybe at certain points.

foldToMaybeWithIndexTree :: (b -> b -> b) -> (Int -> Elem y -> b) -> Int -> FingerTree (Elem y) -> Maybe b Source

A foldMapWithIndex-like function, specialized to the Option monoid, which takes advantage of the internal structure of Seq to avoid wrapping in Maybe at certain points.