sort

File sort.str
Author unknown
Since unknown

This module contains strategies for sorting lists.

qsort is the easiest strategy to use for sorting lists.

Using SortL, LSort and sort-list, isort-list, you can compose your own sorting routine.

Additionally, LMerge can be used with sort-list andisort-list to do list folding.




Statistics


General
Lines of code 133
Stratego
Module number 1 (100% documented)
Constructor number 0
Overlay number 0
Strategy number 6 (66% documented)
Rule number 5 (60% documented)
DynamicRule number 0



Strategy summary


isort-list(Strategy s) Sorts a list when given a suitable comparsion strategy s sort.str
qsort(Strategy swap) Sort a list using the quick-sort algorithm sort.str
quick-sort(Strategy swap) n/a sort.str
sort-list(Strategy s) Sorts a list when given a suitable comparsion strategy s sort.str
uniq n/a sort.str

Rule summary


LMerge(Strategy s) Merges the first and a particular element of the list, determined by the strategy argument s sort.str
LSort(Strategy s) Moves a particular element of a list to the front, determined by the strategy argument s sort.str
quick-sort(Strategy swap, ATerm tail) n/a sort.str
quick-sort(Strategy swap, ATerm tail) n/a sort.str
SortL(Strategy s) Swaps the two first elements in a list if s succeeds on this pair sort.str



Strategy details


ATerm isort-list(Strategy s)
File sort.str
Author unknown
Since unknown
 
Parameters
Strategy s s List(a) -> List(a)

Sorts a list when given a suitable comparsion strategy s. The strategy s should be selected from LSort, SortL and LMerge.

Example: <isort-list(LSort(gt))> [3,5,6,1] => [1,3,5,6]Example: <isort-list(LMerge(add))> [3,6,5,1] => [15]


type List(a) -> List(a)

 
ATerm qsort(Strategy swap)
File sort.str
Author unknown
Since unknown
 
Parameters
Strategy swap swap (a, a) -> _

Sort a list using the quick-sort algorithm.

qsort(lt) sorts a list of integers in ascending order.


type List(a) -> List(a)

 
ATerm sort-list(Strategy s)
File sort.str
Author unknown
Since unknown
 
Parameters
Strategy s s List(a) -> List(a)

Sorts a list when given a suitable comparsion strategy s. The strategy s should be selected from LSort, SortL and LMerge.

Example: <sort-list(LSort(gt))> [3,5,6,1] => [1,3,5,6]Example: <sort-list(LMerge(add))> [3,6,5,1] => [15]


type List(a) -> List(a)

 

Rule details


ATerm LMerge(Strategy s)
File sort.str
Author unknown
Since unknown
 
Parameters
Strategy s s a * b -> c

Merges the first and a particular element of the list, determinedby the strategy argument s. Let x be the first element of the list,and y be selected in succession from the tail. s will be appliedto (x,y) in turn, and when it succeeds, the result will be placedat the head of the list, replacing x.

Example: LMerge(gt ; add)> [3,5,6,1] => [4,5,6]


type List(a) -> List(c | a)

 
ATerm LSort(Strategy s)
File sort.str
Author unknown
Since unknown
 
Parameters
Strategy s s a * b -> _

Moves a particular element of a list to the front, determined bythe strategy argument s. Given the first element of the list x, each succeeding element y will be compared to x using <s> (x,y).The first y that makes s succeed, is moved to the front.

Example: <LSort(gt)> [3,5,6,1] => [1,3,5,6]

Here, 3 is compared with 5, 6, using gt, and will fail in bothcases. <gt> (3,1) will succeed, and 1 will be moved to thefront of the list.


type List(a) -> List(a)

 
ATerm SortL(Strategy s)
File sort.str
Author unknown
Since unknown
 
Parameters
Strategy s s a * b -> _

Swaps the two first elements in a list if s succeeds on this pair.As the swapping occurs if the predicate succeeds, lt and gt willseem to have inverse semantics.

This rule is designed to plug into sort-list and isort-list. Seethese strategies for examples.

Example: <SortL(gt)> [3,1,2,4] => [1,3,2,4]


type List(a) -> List(a)