.. Mars Documentation
   Copyright (C) 2013 Matt Giuca

.. This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

.. This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

.. You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.

:mod:`set` --- Unordered set type
=================================

.. sectionauthor:: Matt Giuca <matt.giuca@gmail.com>
.. moduleauthor::  Matt Giuca <matt.giuca@gmail.com>

.. module:: set
   :synopsis: An unordered set data type and operations.

The :type:`Set` type allows the representation of an unordered set of values,
with efficient insertion and lookup. Being represented internally as a hash
table, membership can be tested in amortised O(1) time. As with arrays,
insertion is non-destructive and requires that a copy of the set is made.

.. type:: Set(a)

   A set of values, with no duplicates or ordering. All values have the same
   type *a*.

   .. note::

      The :func:`eq` function should not be used to test if two sets are
      equal, as it may return false negatives. This is because two sets may
      have the same values, but a different internal hash table arrangement.
      Instead, use :func:`set_eq`.

.. function:: set_init(capacity :: Num) :: Set(a)

   Creates an empty set, with *capacity* as the initial capacity for the hash
   table. The *capacity* has no bearing on the semantics of the set, since it
   will be automatically expanded if it runs out of room.

.. function:: set_empty(set :: Set(a)) :: Num

   Tests if *set* is empty. 1 if it is empty, 0 otherwise.

.. function:: set_length(set :: Set(a)) :: Num

   The number of elements in *set*.

.. function:: set_capacity(set :: Set(a)) :: Num

   The capacity of *set*. This has no bearing on the semantics of *set*, since
   it will be automatically expanded if it runs out of room. This shows the
   current size of the internal hash table.

.. function:: set_insert(set :: Set(a), value :: a) :: Set(a)

   Inserts a *value* into *set*, non-destructively. Returns a new, updated
   set. If *value* is already in *set*, this simply returns *set* unmodified.

.. function:: set_member(set :: Set(a), item :: a) :: Num

   Returns 1 if any element of *set* compares equal (according to :func:`eq`)
   to *item*; 0 otherwise. This performs an efficient hash table lookup.

.. function:: array_to_set(array :: Array(a)) :: Set(a)

   Convert *array* to a :type:`Set` of the same elements. This discards
   duplicate elements.

.. function:: set_to_array(set :: Set(a)) :: Array(a)

   Convert *set* to an :type:`Array` of the same elements.

   .. note::

      The order of the elements in the resulting array is undefined. It should
      not be relied upon.


.. function:: set_eq(xs :: Set(a), ys :: Set(a)) :: Num

   Determine whether *xs* and *ys* contain the same elements. This is
   preferred over :func:`eq`, because it compares the set elements without
   regards to the order they were inserted. For example, ``array_to_set([8,
   13])`` may not equal ``array_to_set([13, 8])``, but those sets will compare
   equal under this function.

   Note that this uses :func:`eq` to compare the set elements, so it will not
   correctly compare a set of sets.

.. function:: set_union(xs :: Set(a), ys :: Set(a)) :: Set(a)

   Finds the union of *xs* and *ys*. The resulting set contains all of the
   elements that appear in either set.

.. function:: set_intersection(xs :: Set(a), ys :: Set(a)) :: Set(a)

   Finds the intersection of *xs* and *ys*. The resulting set contains only
   the elements that appear in both sets.