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.
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) | ||||||||||||||
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]
|
|||||||||||||||
ATerm | qsort(Strategy swap) | ||||||||||||||
Sort a list using the quick-sort algorithm. qsort(lt) sorts a list of integers in ascending order.
|
|||||||||||||||
ATerm | sort-list(Strategy s) | ||||||||||||||
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]
|
|||||||||||||||
Rule details |
|||||||||||||||
ATerm | LMerge(Strategy s) | ||||||||||||||
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]
|
|||||||||||||||
ATerm | LSort(Strategy s) | ||||||||||||||
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.
|
|||||||||||||||
ATerm | SortL(Strategy s) | ||||||||||||||
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]
|
|||||||||||||||