/** * 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@strategoxt.org> - 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) }) )