/** * 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 and * isort-list to do list folding. */ module collection/list/sort imports collection/list/common rules /** * 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 will * seem to have inverse semantics. * * This rule is designed to plug into sort-list and isort-list. See * these strategies for examples. * * Example: <SortL(gt)> [3,1,2,4] => [1,3,2,4] * * @param s a * b -> _ * @type List(a) -> List(a) */ SortL(s) : [x, y | l] -> [y, x | l] where <s> (x, y) /** * Moves a particular element of a list to the front, determined by * the 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 both * cases. <gt> (3,1) will succeed, and 1 will be moved to the * front of the list. * * @param s a * b -> _ * @type List(a) -> List(a) */ LSort(s) : [x | l] -> [y, x | l'] where <at-suffix({ys: ?[y | ys]; where(<s> (x, y)); !ys})> l => l' /** * Merges the first and a particular element of the list, determined * by 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 applied * to (x,y) in turn, and when it succeeds, the result will be placed * at the head of the list, replacing x. * * Example: LMerge(gt ; add)> [3,5,6,1] => [4,5,6] * * @param s a * b -> c * @type List(a) -> List(c | a) */ LMerge(s) : [x | l] -> [z | l'] where <at-suffix(\ [y | ys] -> ys where <s> (x, y) => z\ )> l => l' strategies /** * 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] * * @param s List(a) -> List(a) * @type List(a) -> List(a) */ sort-list(s) = try(rec x((s <+ [id | x]); try(x))) /** * 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] * * @param s List(a) -> List(a) * @type List(a) -> List(a) */ isort-list(s) = try(rec x(([id | x] <+ s); try(x))) /** @internal */ jsort-list(s) = try(rec x([id | x] <+ s; try(x))) /** * Removes duplicates from a list, returning a list of mutually unique terms. * * @type List(a) -> List(a) * * @inc tuple-uniq-test */ uniq = let Uniq = \ [x | xs] -> [x | <filter(not(?x))> xs] \ in listtd(try(Uniq)) end strategies /** * Sort a list using the quick-sort algorithm. * * qsort(lt) sorts a list of integers in ascending order. * * @param swap (a, a) -> _ * @type List(a) -> List(a) */ qsort(swap) = let swapper(|a2) = <swap> (<id>, a2) in quick-sort(swapper) end /** * Quick-sort without tuples and concats. */ strategies quick-sort(swap : a * a -> b) = quick-sort(swap | []) quick-sort(swap : a * a -> b | tail) : [] -> tail quick-sort(swap: a * a -> b | tail) : [x | xs] -> <quick-sort(swap | [x | tail'])> smaller where smaller := <retain-all(where(swap(|x)))> xs => a ; bigger := <remove-all(where(swap(|x)))> xs ; tail' := <quick-sort(swap | tail)> bigger