1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
\DOC sort
\TYPE {sort : (((* # *) -> bool) -> * list -> * list)}
\SYNOPSIS
Sorts a list using a given transitive `ordering' relation.
\DESCRIBE
The call
{
sort op list
}
\noindent where {op} is an (uncurried) transitive relation on the elements of
{list}, will topologically sort the list, i.e. will permute it such that if
{x op y} but not {y op x} then {x} will occur to the left of {y} in the
sorted list. In particular if {op} is a total order, the list will be sorted in
the usual sense of the word.
\FAILURE
Never fails.
\EXAMPLE
A simple example is:
{
#sort $< [3; 1; 4; 1; 5; 9; 2; 6; 5; 3; 5; 8; 9; 7; 9];;
[1; 1; 2; 3; 3; 4; 5; 5; 5; 6; 7; 8; 9; 9; 9] : int list
}
\noindent The following example is a little more complicated. Note
that the `ordering' is not antisymmetric.
{
#sort ($< o (fst # fst)) [(1,3); (7,11); (3,2); (3,4); (7,2); (5,1)];;
[(1, 3); (3, 4); (3, 2); (5, 1); (7, 2); (7, 11)] : (int # int) list
}
\ENDDOC
|
