/**
 * This module contains strategies for operating on tuples.
 *
 * In Stratego, tuples are a terms, separate from lists. 
 *
 * @author Eelco Visser <visser@acm.org>
 * @author Karl Trygve Kalleberg <karltk@cs.uu.nl> - documentation
 *
 * @see collection/list/common
 */
module collection/tuple/common 
imports 
  collection/list/cons 
  collection/tuple/cons 
  collection/list/index 
  collection/list/zip
strategies

  /** Convert a tuple to a list.
   *
   * @type List(a) -> Tuple(a)
   */
  TupleToList : "" # (xs) -> xs
  
  /** Convert a list to a tuple.
   *
   * @type Tuple(a) -> List(a)
   */
  ListToTuple : xs -> "" # (xs)

  /** Retrieve the first element of a tuple.
   *
   * @type Tuple(a, xs...) -> a
   */
  Fst   : "" # ([x | xs]) -> x
  
  /** Retrieve the second element of a tuple.
   *
   * @type Tuple(a, b, xs...) -> b
   */
  Snd   : "" # ([x, y | xs]) -> y

  /** Retrieve the third element of a tuple.
   *
   * @type Tuple(a, b, c, xs...) -> c
   */
  Third : "" # ([x, y, z | xs]) -> z

  /** Duplicate a term into a two-element tuple
   *
   * @type a -> Tuple(a, a)
   */
  Dupl  : x -> (x, x)

  /** Apply a pair of strategies, f and g, to a two-element tuple. The 
   * strategy f will be applied to the first element, g to the second.
   *
   * @param f        a -> a'
   * @param g        b -> b'
   * @type           Tuple(a, b) -> Tuple(a', b')
   */
  split(f, g) = !(<f>, <g>)
  
  /** Apply a triple of strategies, f, g and h to a three-element tuple.
   * The strategy f will be applied to the first element, g to the second
   * and h to the third.
   *
   * @param f        a -> a'
   * @param g        b -> b'
   * @param h        c -> c'
   * @type           Tuple(a, b, c) -> Tuple(a', b', c')
   */
  split3(f, g, h) = !(<f>, <g>, <h>)

  /** Swap two elements in a tuple.
   *
   * @type Tuple(a, b) -> Tuple(b, a)
   */
  Swap : (x, y) -> (y, x)

  /** Retrieve the head of a tuple. 
   * 
   * @type Tuple(a) -> a
   * @see Fst
   */
  Thd = Fst
  
  /** Retrieve the tail of a tuple. A new tuple with all elements except
   * the first will be returned.
   * 
   * @type Tuple(a) -> Tuple(a)
   */
  Ttl : "" # ([x | xs]) -> "" # (xs)

  /** Get the nth element of a tuple. The index must be smaller than the
   * number of elements in the tuple.
   *
   * @type (Int, Tuple(a)) -> a
   * @see index
   */
  tindex = 
    (id, ?""#(<id>)); index

  /** Predicate that checks if the supplied term is a tuple.
   *
   * @type Tuple(a) -?> Tuple(a)
   */
  is-tuple = 
    ?""#(_)

  /** Apply a strategy s to a swapped version of the supplied tuple.
   * The supplied tuple will be swapped, then is s applied.
   *
   * @param s          Tuple(b,a) -> Tuple(b', a')
   * @type             Tuple(a,b) -> Tuple(b', a')
   */
  flip(s) = Swap; s

  /** Apply a strategy to each element of a tuple. This strategy maps
   * a strategy s over all elements in a tuple.
   *
   * @param s           a -> b
   * @type              Tuple(a) -> Tuple(b)
   */
  tmap(s) = 
    is-tuple; all(s)

  /** Concatenate the lists in a tuple of lists, using s as the
   * concatenation strategy.
   *
   * The concatenation strategy is asked to concatenate a two-element
   * tuple of lists and produce a list. Concatenation goes from right to
   * left.
   *
   * @param s          Tuple(List(a), List(a)) -> List(a)
   * @type             Tuple(List(a))
   */
  tconcat(s) = 
    is-tuple; crush(![], s)

  /** Concatenate the lists in a tuple of lists, using s2 as the
   * concatenation strategy and s1 as the startup strategy.
   *
   * The strategy s1 is applied once initially to an empty list, and
   * can be used to create a custom tail on the resulting list. It can
   * also be used to concatenate into non-list types.
   * 
   * The concatenation strategy s2 is asked to concatenate a
   * two-element tuple of lists and produce list. Concatenation goes
   * from right to left.
   *
   * Example: <tconcat'(!0, \([a],b)-><add> (a,b)\)> ([1],[2],[3]) => 6
   *
   * @param s1         Nil -> b
   * @param s2         Tuple(List(a), b) -> b
   * @type             Tuple(List(a))
   * @see tconcat
   */
  tconcat'(s1, s2) = 
    is-tuple; crush(<s1> [], s2)

  /** Apply a s1 and s2 in a catamorphic way to reduce a tuple.
   * 
   * s2 must be a catamorphism, i.e. it must be able to reduce the 
   * elements of the tuple from right to left.
   *
   * This strategy is also named tfoldr, as it is equivalent to a 
   * right-fold on tuples.
   * 
   * @param s1         Nil -> b
   * @param s2         Tuple(a, b) -> b
   * @type             Tuple(a) -> b
   * @see foldr
   */
  tcata(s1, s2) = 
    is-tuple; crush(s1, s2)

  /**
   * Fold a tuple from right to left using s2 as the folding strategy. 
   * s1 is used to obtain the right-element (of type b) for s2. 
   * 
   * @param s1         Nil -> b
   * @param s2         Tuple(a, b) -> b
   * @type             Tuple(a) -> b
   * @see tcata
   */
  tfoldr(s1, s2) = 
    tcata(s1, s2)

  /** Zip two tuples with s as the zipping strategy. 
   *
   * Example: <tzip(add)> ((1,2,3),(5,4,3)) -> [6,6,6]
   *
   * @param s          Tuple(a,b) -> c
   * @type             Tuple(Tuple(a), Tuple(b)) -> c
   * @see zip
   */
  tzip(s)  = 
    (TupleToList, TupleToList); zip(s)

  /**
   * @inc tuple-zip-test
   */
  tuple-zip(s) = 
    rec x(![<tmap(Hd); s> | <tmap(Tl); x>]
          <+ tmap([]); ![])

  /**
   * @inc tuple-unzip-test
   */
  tuple-unzip(s) =
    rec x(![<map(Thd); s> | <map(Ttl); x>] <+ map(()); ![])
  ; !"" #(<id>)