sort module:Data.List

The sort function implements a stable sorting algorithm. It is a special case of sortBy, which allows the programmer to supply their own comparison function. Elements are arranged from lowest to highest, keeping duplicates in the order they appeared in the input. The argument must be finite.

Examples

>>> sort [1,6,4,3,2,5]
[1,2,3,4,5,6]

>>> sort "haskell"
"aehklls"

>>> import Data.Semigroup(Arg(..))

>>> sort [Arg ":)" 0, Arg ":D" 0, Arg ":)" 1, Arg ":3" 0, Arg ":D" 1]
[Arg ":)" 0,Arg ":)" 1,Arg ":3" 0,Arg ":D" 0,Arg ":D" 1]

Sort a stream.

Sorts the list. On data types that do not preserve ordering, or enforce their own ordering, the result may not be what you expect. See also sortBy.

The sort function implements a stable sorting algorithm. It is a special case of sortBy, which allows the programmer to supply their own comparison function.

The sortBy function is the non-overloaded version of sort. The argument must be finite. The supplied comparison relation is supposed to be reflexive and antisymmetric, otherwise, e. g., for _ _ -> GT, the ordered list simply does not exist. The relation is also expected to be transitive: if it is not then sortBy might fail to find an ordered permutation, even if it exists.

Examples

>>> sortBy (\(a,_) (b,_) -> compare a b) [(2, "world"), (4, "!"), (1, "Hello")]
[(1,"Hello"),(2,"world"),(4,"!")]

Sort a list by comparing the results of a key function applied to each element. sortOn f is equivalent to sortBy (comparing 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. Elements are arranged from lowest to highest, keeping duplicates in the order they appeared in the input. The argument must be finite.

Examples

>>> sortOn fst [(2, "world"), (4, "!"), (1, "Hello")]
[(1,"Hello"),(2,"world"),(4,"!")]

>>> sortOn length ["jim", "creed", "pam", "michael", "dwight", "kevin"]
["jim","pam","creed","kevin","dwight","michael"]

Performance notes

This function minimises the projections performed, by materialising the projections in an intermediate list. For trivial projections, you should prefer using sortBy with comparing, for example:

>>> sortBy (comparing fst) [(3, 1), (2, 2), (1, 3)]
[(1,3),(2,2),(3,1)]

Or, for the exact same API as sortOn, you can use `sortBy . comparing`:

>>> (sortBy . comparing) fst [(3, 1), (2, 2), (1, 3)]
[(1,3),(2,2),(3,1)]

sortBy for NonEmpty, behaves the same as sortBy

Sort a NonEmpty on a user-supplied projection of its elements. See sortOn for more detailed information.

Examples

>>> sortOn fst $ (2, "world") :| [(4, "!"), (1, "Hello")]
(1,"Hello") :| [(2,"world"),(4,"!")]

>>> sortOn List.length ("jim" :| ["creed", "pam", "michael", "dwight", "kevin"])
"jim" :| ["pam","creed","kevin","dwight","michael"]

Performance notes

This function minimises the projections performed, by materialising the projections in an intermediate list. For trivial projections, you should prefer using sortBy with comparing, for example:

>>> sortBy (comparing fst) $ (3, 1) :| [(2, 2), (1, 3)]
(1,3) :| [(2,2),(3,1)]

Or, for the exact same API as sortOn, you can use `sortBy . comparing`:

>>> (sortBy . comparing) fst $ (3, 1) :| [(2, 2), (1, 3)]
(1,3) :| [(2,2),(3,1)]

sortWith is an alias for `sortBy . comparing`.

sortWith for NonEmpty, behaves the same as:

sortBy . comparing

Sort by comparing the results of a function applied to each element. The sort is stable, and the function is evaluated only once for each element.

Sort a NonEmpty on a user-supplied projection of its elements. See sortOn for more detailed information.

Examples

>>> sortOn fst $ (2, "world") :| [(4, "!"), (1, "Hello")]
(1,"Hello") :| [(2,"world"),(4,"!")]

>>> sortOn length $ "jim" :| ["creed", "pam", "michael", "dwight", "kevin"]
"jim" :| ["pam","creed","kevin","dwight","michael"]

Performance notes

This function minimises the projections performed, by materialising the projections in an intermediate list. For trivial projections, you should prefer using sortBy with comparing, for example:

>>> sortBy (comparing fst) $ (3, 1) :| [(2, 2), (1, 3)]
(1,3) :| [(2,2),(3,1)]

Or, for the exact same API as sortOn, you can use `sortBy . comparing`:

>>> (sortBy . comparing) fst $ (3, 1) :| [(2, 2), (1, 3)]
(1,3) :| [(2,2),(3,1)]

sortWith is an alias for `sortBy . comparing`. Since: 4.20.0.0

Sort function taking a custom comparison function

The sortBy function is the non-overloaded version of sort.

The sortOn function provides the decorate-sort-undecorate idiom, also known as the "Schwartzian transform".

This variant of sortOn recomputes the sorting key every comparison. This can be better for functions that are cheap to compute. This is definitely better for projections, as the decorate-sort-undecorate saves nothing and adds two traversals of the list and extra memory allocation.

O(n). Whether the elements are in sorted order.

>>> sorted [1, 2, 3, 3]
True

>>> sorted [1, 2, 3, 2]
False

>>> sorted []
True

>>> sorted [1]
True

O(n). Like sorted, with a custom comparison test.

>>> sortedBy (comparing Down) [3, 2, 1]
True

>>> sortedBy (comparing Down) [3, 2, 1, 2]
False