/**
 * 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