Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell98 |
WARNING
This module is considered internal.
The Package Versioning Policy does not apply.
The contents of this module may change in any way whatsoever and without any warning between minor versions of this package.
Authors importing this module are expected to track development closely.
Description
This module provides the various sorting implementations for Data.Sequence. Further notes are available in the file sorting.md (in this directory).
Synopsis
- sort :: Ord a => Seq a -> Seq a
- sortBy :: (a -> a -> Ordering) -> Seq a -> Seq a
- sortOn :: Ord b => (a -> b) -> Seq a -> Seq a
- unstableSort :: Ord a => Seq a -> Seq a
- unstableSortBy :: (a -> a -> Ordering) -> Seq a -> Seq a
- unstableSortOn :: Ord b => (a -> b) -> Seq a -> Seq a
- data Queue e = Q !e (QList e)
- data QList e
- data IndexedQueue e = IQ !Int !e (IQList e)
- data IQList e
- = IQNil
- | IQCons !(IndexedQueue e) (IQList e)
- data TaggedQueue a b = TQ !a b (TQList a b)
- data TQList a b
- = TQNil
- | TQCons !(TaggedQueue a b) (TQList a b)
- data IndexedTaggedQueue e a = ITQ !Int !e a (ITQList e a)
- data ITQList e a
- = ITQNil
- | ITQCons !(IndexedTaggedQueue e a) (ITQList e a)
- mergeQ :: (a -> a -> Ordering) -> Queue a -> Queue a -> Queue a
- mergeIQ :: (a -> a -> Ordering) -> IndexedQueue a -> IndexedQueue a -> IndexedQueue a
- mergeTQ :: (a -> a -> Ordering) -> TaggedQueue a b -> TaggedQueue a b -> TaggedQueue a b
- mergeITQ :: (a -> a -> Ordering) -> IndexedTaggedQueue a b -> IndexedTaggedQueue a b -> IndexedTaggedQueue a b
- popMinQ :: (e -> e -> Ordering) -> Queue e -> (Queue e, e)
- popMinIQ :: (e -> e -> Ordering) -> IndexedQueue e -> (IndexedQueue e, e)
- popMinTQ :: (a -> a -> Ordering) -> TaggedQueue a b -> (TaggedQueue a b, b)
- popMinITQ :: (e -> e -> Ordering) -> IndexedTaggedQueue e b -> (IndexedTaggedQueue e b, b)
- buildQ :: (b -> b -> Ordering) -> (a -> Queue b) -> FingerTree a -> Maybe (Queue b)
- buildIQ :: (b -> b -> Ordering) -> (Int -> Elem y -> IndexedQueue b) -> Int -> FingerTree (Elem y) -> Maybe (IndexedQueue b)
- buildTQ :: (b -> b -> Ordering) -> (a -> TaggedQueue b c) -> FingerTree a -> Maybe (TaggedQueue b c)
- buildITQ :: (b -> b -> Ordering) -> (Int -> Elem y -> IndexedTaggedQueue b c) -> Int -> FingerTree (Elem y) -> Maybe (IndexedTaggedQueue b c)
- foldToMaybeTree :: (b -> b -> b) -> (a -> b) -> FingerTree a -> Maybe b
- foldToMaybeWithIndexTree :: (b -> b -> b) -> (Int -> Elem y -> b) -> Int -> FingerTree (Elem y) -> Maybe b
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.
is
equivalent to sortOn
f
, but has the
performance advantage of only evaluating sortBy
(compare
`on
` f)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
),
will be faster than
sortBy
(compare
`on
` f)
.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.
is equivalent to unstableSortOn
f
,
but has the performance advantage of only evaluating unstableSortBy
(compare
`on
` f)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
),
will be faster than
unstableSortBy
(compare
`on
` f)
.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 IndexedQueue e Source #
A pairing heap tagged with the original position of elements, to allow for stable sorting.
data TaggedQueue a b Source #
A pairing heap tagged with some key for sorting elements, for use
in unstableSortOn
.
data IndexedTaggedQueue e a Source #
A pairing heap tagged with both a key and the original position
of its elements, for use in sortOn
.
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.
mergeIQ :: (a -> a -> Ordering) -> IndexedQueue a -> IndexedQueue a -> IndexedQueue a Source #
mergeIQ
merges two IndexedQueue
s, 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 TaggedQueue
s, based on the tag value.
mergeITQ :: (a -> a -> Ordering) -> IndexedTaggedQueue a b -> IndexedTaggedQueue a b -> IndexedTaggedQueue a b Source #
mergeITQ
merges two IndexedTaggedQueue
s, 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.
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 #
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.