/**
 * This module contains strategies for dealing with sets.
 *
 * The strategies in this module assume that sets are encoded as lists.
 * A list is converted to a set by excising duplicates, using the 
 * make-set strategy .
 *
 * An implementation of indexed sets can be found in collection/set/indexed.
 *
 * Given this notion of sets, we can perform the traditional
 * set operations such as intersect (isect), union, one-way
 * difference (diff) and symmetric difference (sym-diff). 
 *
 * We can also check sets for equality (set-eq), strict and 
 * non-strict subset relation (subset and subseteq, respectively).
 *
 * @author Eelco Visser <visser@acm.org>
 * @author Karl Trygve Kalleberg <karltk@cs.uu.nl> - documentation
 *
 * @see collection/set/indexed
 */
module collection/list/set
imports 
  collection/list/common 
  term/common
  strategy/collect // collect is imported for backwards compatibility

rules
 
  /** @internal */
  HdMember(mklst) : 
    [x | xs] -> xs where mklst; fetch(?x)

  /** @internal */
  HdMember'(eq, mklst) : 
     [x | xs] -> xs 
     where mklst; fetch(\y -> <eq> (x, y)\)

strategies

  /**
   * Removes duplicate elements from a list. This effectively
   * converts a list to a set.
   *
   * @type  List(a) -> List(a)
   */
  make-set =
    foldr(![], union, ![<id>])

  /**
   * Removes duplicate elements from a list. This effectively
   * converts a list to a set.
   *
   * @type   List(a) -> List(a)
   * @note   nub is an alias of make-set.
   * @since  0.9.4
   */
  nub = make-set

strategies

  /**
   * Union: Concatenation of two lists, only those elements in the
   * first list are added that are not already in the second list.
   *
   * @type List(a) * List(a) -> List(a)
   * @inc  test1a
   * @inc  test1b
   * @inc  test1c
   * @inc  test1d
   * @inc  test1e
   */
  union = union(eq)

  // a * a -> fail? :: List(a) * List(a) -> List(a)
  /**
   * Takes the union of two sets. The result is a set
   * where all elements found in both sets are present,
   * but each element occurs only once. The strategy
   * parameter is the equality operator to be used on the 
   * elements.
   *
   * @param Equality operator to be used on the elements
   * @type List(a) * List(a) -> List(a)
   */
  union(eq) : 
    (l1, l2) -> <rec x(
                   ([]; !l2)
                <+ (HdMember'(eq, !l2); x)
                <+ [id | x]
                )> l1

strategies

  /**
   * Takes the union of a list of sets. All the sets are
   * sets are flattened into one list, and all duplicates
   * are removed, to obtain a new set.
   *
   * Example: <unions> [[1,2,3],[3,4,5],[5,6,7]] => [1,2,3,4,5,6,7]
   *
   * @type  List(List(a)) -> List(a)
   */
  unions = unions(eq)

  // a * a -> fail? :: List(List(a)) -> List(a)
  /**
   * Takes the union of a list of sets. The result is a set
   * where all elements found in either of the sets are present,
   * i.e. where each element occurs only once. The strategy
   * parameter is the equality operator to be used on the 
   * elements.
   *
   * @param Equality operator used on the elements.
   * @type List(List(a)) -> List(a)
   */
  unions(eq) = foldr(![], union(eq))

rules

  /**
   * Computes the difference between two sets. That is, it
   * returns the elements found in the first set, but not in
   * the second.
   *
   * @type  (List(a), List(a)) -> List(a)
   * @inc  test3a
   * @inc  test3b
   * @inc  test3c
   * @inc  test3d
   * @inc  test3e
   */ 
  diff = diff(eq) 

  /**
   * Computes the difference between two sets. That is, the elements
   * found in the first set, but not in the second. The strategy 
   * argument is used to compare elements of the sets.
   *
   * Example: <diff(eq)> ([1,2,3], [5,1,2]) => [3]
   * 
   * @param  Used to compare the elements. If an application succeeds, then two elements are equal.
   * @type   (List(a), List(a)) -> List(a)
   */
  diff(eq) :
    (l1, l2) -> <rec x(
                   []
                <+ (HdMember'(eq, !l2); x)
                <+ [id | x]
                )> l1

  /**
   * Takes the symmetric difference of two sets. That is, it returns
   * all elements not found in both sets.
   *
   * Example: <sym-diff> ([1,2,3],[5,1,2,6]) => [3,5,6]
   *
   * @type  (List(a), List(a)) -> List(a)
   * @inc  test4a
   * @inc  test4b
   * @inc  test4c
   * @inc  test4d
   * @inc  test4e
   */
  sym-diff = sym-diff(eq)

  /**
   * Takes the symmetric difference of two sets. That is, it returns
   * all elements not found in both sets. the strategy argument is
   * used to compare elements of the sets.
   *
   * Example: <sym-diff(eq)> ([1,2,3],[5,1,2,6]) => [3,5,6]
   *
   * @param  Equality operator to use on the elements. If it succeeds, the elements are equal.
   * @type   (List(a), List(a)) -> List(a)
   */
  sym-diff(eq) =
    <union> (<diff(eq)>, <Swap; diff(eq)>)

strategies

  /**
   * Take the intersection of two sets. That is, it returns
   * all elements found in both sets. 
   *
   * Example: <isect> ([1,2,3],[5,1,2,6]) => [1,2]
   *
   * @type List(a) * List(a) -> List(a)
   * @inc  test2a
   * @inc  test2b
   * @inc  test2c
   * @inc  test2d
   * @inc  test2e
   */
  isect = isect(eq)


  /**
   * Take the intersection of two sets.
   *
   * The result is the first list, without the elements
   * that are not in the second list. If the first list is not
   * a set (it has duplicates), the result will
   * have duplicates. Note that because of this <isect> (l1, l2) is 
   * not always equal to <isect> (l2, l1).
   *
   * @type eq  a * a ->? _ 
   * @type     [a] * [a] -> [a]
   */
  isect(eq) : 
    (l1, l2) -> <rec x(
                   [] 
                <+ ( where(HdMember'(eq, !l2)); [id | x] )
                <+ ?[_ | <x>]
                )> l1

strategies


  /**
   * Check equality of two list sets.
   *
   * This strategy uses the basic `eq` to compare the elements.
   */
  set-eq = set-eq(eq)

  /**
   * Check equality of two list sets.
   *
   * The input remains untouched, set-eq just succeeds or fails.
   *
   * @param test strategy that will compare two elements upon their equality.
   * @inc set-eq-test1
   * @inc set-eq-test2
   * @inc set-eq-test3
   * @inc set-eq-test4
   * @inc set-eq-test5
   */
  set-eq(eq)   = subset-gen(eq, ?[])

  /**
   * Succeeds if the first set is a strict subset of the second.
   * 
   * Example: <subset> ([1,2],[1,2,3])
   *
   * @type List(a) * List(a) -> _
   */
  subset       = subset(eq)

  /**
   * Succeeds if the first set is a strict subset of the second. The 
   * strategy parameter is the equality operator that will be used
   * to check if two elements are equal.
   *
   * @param Equality operator to be used on elements on the set. 
   * @type List(a) -> List(a) -> _
   */
  subset(eq)   = subset-gen(eq, ?[_|_])

  /** 
   * Succeeds if the first set is a (non-strict) subset of the second.
   * 
   * Example: <subseteq> ([1,2],[1,2])
   *
   * @type List(a) * List(a) -> _
   */
  subseteq     = subseteq(eq)

  /** 
   * Succeeds if the first set is a (non-strict) subset of the second.
   * The strategy parameter is the equality operator that will be used
   * to check if two elements are equal.
   * 
   * Example: <subseteq> ([1,2],[1,2])
   *
   * @type List(a) * List(a) -> _
   */
  subseteq(eq) = subset-gen(eq, ?[] + ?[_|_])

  /**
   * General strategy for comparing two list sets.
   *
   * Other strategies call this one to check for equality, subset or subseteq.
   *
   * @param Equality operator to be used on elements in the set.
   * @param Matching strategy that tests the remainder of the right (2nd)
   *        set after comparing all elements from the first list.
   */
  subset-gen(eq, rest) =
    where(
      rec r ( {x, xs, y, ys, y*:
        ([],rest)
      + ?([x|xs], y* )
      ; <split-fetch(\ y -> <eq> (x, y)\); conc> y* => ys
      ; <r> (xs, ys)
      })
    )