Description of the Bag Concept

H. Conrad Cunningham, Professor
Department of Computer and Information Science
University of Mississippi

04 December 2013

I adapted this description from the header comments for the Scala
CookieJar trait developed in March 2010 and modified in January 2012
for the course Mulitparadigm Programming (CSci 556).

I use notation that can be typed into comments for computer programs,
not the notation that would be used in a typeset mathematics textbook.

123456789012345678901234567890123456789012345678901234567890123456789012345678

A mathematical bag is an unordered collection of values in which each
value may occur one or more times.

The bag notation used in this documentation includes:

  {| |} denotes empty bag

  {| 2, 3, 2, 1 |} denotes a bag with four elements including two 2's,
    one 3, and one 1.  The order is not significant!  There may be one
    or more occurrences of an element.

  IN denotes the bag membership operation.  x IN B if there are one or
    more occurrences of the value x in bag B.

  UNION denotes bag union.  The resulting bag has the total number of
    occurrences of elements from the two bags.  {| 3, 1, 1, 3 |} UNION
    {| 1, 2 |] = [| 1,1,1,2,3,3 |} (Remember order is not
    significant.)

  DIFF denotes bag difference.  A DIFF B removes each occurrence of
    elements in B from A.  The resulting bag has the number of
    occurrences in bag A minus the number of occurrences in bag B.  If
    there are more occurrence in B than A, then the result has no
    occurrences. {| 1, 1, 2, 1 }} DIFF {| 2,1,1 |} = {| 1 |}

  OCCURRENCES denotes occurrence counting.  OCCURENCES(x,B) returns
    the number of times element x appears in bag B.