/** * This module contains strategies for handling bags. * * A bag is a set of elements where each element has an occurence number. Adding * an element to a bag which already exists, will increase the occurence number * for that element by one. * * In the current implementation, bags are represented as lists of * (element,occurrence) tuples. Adding a new element is done using bag-insert. */ module collection/list/bag imports collection/list/common rules /** * Inserts a new element into a bag. The element must be on the form * a (element, occurrence) tuple, where occurrence is an integer. The * bag may be empty. * * Example: <bag-insert> (('a', 1), []) => [('a',1)] * * @type (elem, occur) * List(a) -> List(a) */ bag-insert : ((x,j), l) -> <fetch(\ (y,i) -> (y, <add>(i,j)) where <eq>(y,x) \ ) <+ ![(x,j)|l]> l /** * Takes the union of two bags. * * Example: <bag-union> ([('a',2), ('b',1)], [('a',1)]) => [('b',1),('a',3)] * * @type List(a) * List(a) -> List(a) */ bag-union : (l1, l2) -> <foldr(!l2, bag-insert)> l1 /** * Inserts a new element into a bag. The element must be on the form * a (element, occurrence) tuple, where occurrence is an integer. The * bag may be empty. The strategy parameter is used to check elements * for equality. * * @param Used to test equality on elements. * @type (elem, occurrence) * List(a) -> List(a) */ bag-insert(equ) : ((x,j), l) -> <fetch(\ (y,i) -> (<equ>(x,y), <add>(i,j)) \ ) <+ ![(x,j)|l]> l /** * Takes the union of two bags. The strategy parameter is used * to check elements for equality. * * @param Used to test equality on elements. * @type List(a) * List(a) -> List(a) */ bag-union(equ) : (l1, l2) -> <foldr(!l2, bag-insert(equ))> l1