Basic data types and related functions used in SNAKES

### Function `cross`

``def cross (sets) :``

Cross-product of some iterable collections (typically, `list` or `set`).

``````>>> list(cross([[1, 2], [3, 4, 5]]))
[(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)]
>>> list(cross([[1, 2], [3, 4, 5], [6, 7, 8, 9]]))
[(1, 3, 6), (1, 3, 7), (1, 3, 8), (1, 3, 9), (1, 4, 6), (1, 4, 7),
(1, 4, 8), (1, 4, 9), (1, 5, 6), (1, 5, 7), (1, 5, 8), (1, 5, 9),
(2, 3, 6), (2, 3, 7), (2, 3, 8), (2, 3, 9), (2, 4, 6), (2, 4, 7),
(2, 4, 8), (2, 4, 9), (2, 5, 6), (2, 5, 7), (2, 5, 8), (2, 5, 9)]
>>> list(cross([[], ]))
[]``````
##### Call API
• `iterable sets`: the sets of values to use
• `return generator`: an iterator over the tuples in the cross-product

### Function `iterate`

``def iterate (value) :``

Like Python's builtin `iter` but consider strings as atomic.

``````>>> list(iter([1, 2, 3]))
[1, 2, 3]
>>> list(iterate([1, 2, 3]))
[1, 2, 3]
>>> list(iter('foo'))
['f', 'o', 'o']
>>> list(iterate('foo'))
['foo']``````
##### Call API
• `object value`: any object
• `return generator`: an iterator on the elements of `value` if is is iterable and is not string, an iterator on the sole `value` otherwise

### Class `WordSet`

``class WordSet (set) :``

A set of words being able to generate fresh words.

#### Method `WordSet.fresh`

``````def fresh (self, add=False, min=1, base="",
allowed="abcdefghijklmnopqrstuvwxyz") : ...``````

Create a fresh word (ie, which is not in the set).

``````>>> w = WordSet(['foo', 'bar'])
>>> list(sorted(w))
['bar', 'foo']
>>> w.fresh(True, 3)
'aaa'
>>> list(sorted(w))
['aaa', 'bar', 'foo']
>>> w.fresh(True, 3)
'baa'
>>> list(sorted(w))
['aaa', 'baa', 'bar', 'foo']``````
##### Call API
• `bool add`: add the created word to the set if `add=True`
• `int min`: minimal length of the new word
• `str base`: prefix of generated words
• `str allowed`: characters allowed in the new word

### Class `MultiSet`

``class MultiSet (hdict) :``

Set with repetitions, ie, function from values to integers.

MultiSets support various operations, in particular: addition (`+`), substraction (`-`), multiplication by a non negative integer (`*k`), comparisons (`<`, `>`, etc.), length (`len`).

#### Method `MultiSet.__init__`

``def __init__ (self, values=[]) :``

Initialise the multiset, adding values to it.

``````>>> MultiSet([1, 2, 3, 1, 2])
MultiSet([...])
>>> MultiSet()
MultiSet([])``````
##### Call API
• `object values`: a single value or an iterable collection of values (strings are not iterated)

#### Method `MultiSet.copy`

``def copy (self) :``

Copy a `MultiSet`

``````>>> m1 = MultiSet([1, 2, 3, 1, 2])
>>> m2 = m1.copy()
>>> m1 == m2 and m1 is not m2
True``````
##### Call API
• `return MultiSet`: a copy of the multiset

#### Method `MultiSet.add`

``def add (self, values, times=1) :``

``````>>> m = MultiSet()
>>> m.add([1, 2, 2, 3], 2)
>>> list(sorted(m.items()))
[1, 1, 2, 2, 2, 2, 3, 3]
>>> list(sorted(m.items()))
[1, 1, 2, 2, 2, 2, 3, 3, 5, 5, 5]``````
##### Call API
• `object values`: the values to add or a single value to add
• `int times`: the number of times each value should be added (must be non-negative)
##### Exceptions
• `ValueError`: when `times` is negative

#### Method `MultiSet.remove`

``def remove (self, values, times=1) :``

Remove values to the multiset.

``````>>> m = MultiSet([1, 2, 2, 3] * 2)
>>> list(sorted(m.items()))
[1, 1, 2, 2, 2, 2, 3, 3]
>>> m.remove(2, 3)
>>> list(sorted(m.items()))
[1, 1, 2, 3, 3]
>>> m.remove([1, 3], 2)
>>> list(sorted(m.items()))
``````
##### Call API
• `object values`: the values to remove or a single value to remove
• `int times`: the number of times each value should be removed (must be non negative)
##### Exceptions
• `ValueError`: when `times` is negative

#### Method `MultiSet.__call__`

``def __call__ (self, value) :``

Number of occurrences of `value`.

``````>>> m = MultiSet([1, 1, 2, 3, 3, 3])
>>> m(1), m(2), m(3), m(4)
(2, 1, 3, 0)``````
##### Call API
• `object value`: the value the count
• `return int`

#### Method `MultiSet.__iter__`

``def __iter__ (self) :``

Iterate over the values, including repetitions. Use `MultiSet.keys` to ignore repetitions.

``````>>> list(sorted(iter(MultiSet([1, 2, 3, 1, 2]))))
[1, 1, 2, 2, 3]``````
##### Call API
• `return generator`: an iterator on the elements

#### Method `MultiSet.items`

``def items (self) :``

Return the list of items with repetitions. The list without repetitions can be retrieved with `MultiSet.key`.

``````>>> m = MultiSet([1, 2, 2, 3])
>>> list(sorted(m.items()))
[1, 2, 2, 3]
>>> list(sorted(m.keys()))
[1, 2, 3]``````
##### Call API
• `return list`: list of items including repetitions

#### Method `MultiSet.__str__`

``def __str__ (self) :``

Return a simple string representation of the multiset

``````>>> str(MultiSet([1, 2, 2, 3]))
'{...}'``````
##### Call API
• `return str`: simple string representation of the multiset

#### Method `MultiSet.__repr__`

``def __repr__ (self) :``

Return a string representation of the multiset that is suitable for `eval`

``````>>> repr(MultiSet([1, 2, 2, 3]))
'MultiSet([...])'``````
##### Call API
• `return str`: precise string representation of the multiset

#### Method `MultiSet.__len__`

``def __len__ (self) :``

Return the number of elements, including repetitions.

``````>>> len(MultiSet([1, 2] * 3))
6``````
##### Call API
• `return int`

#### Method `MultiSet.size`

``def size (self) :``

Return the number of elements, excluding repetitions.

``````>>> MultiSet([1, 2] * 3).size()
2``````
##### Call API
• `return int`

#### Method `MultiSet.__add__`

``def __add__ (self, other) :``

``````>>> MultiSet([1, 2, 3]) + MultiSet([2, 3, 4])
MultiSet([...])``````
##### Call API
• `MultiSet other`: the multiset to add
• `return MultiSet`

#### Method `MultiSet.__sub__`

``def __sub__ (self, other) :``

Substract two multisets. The second multiset must be smaller than the first one.

``````>>> MultiSet([1, 2, 3]) - MultiSet([2, 3])
MultiSet()
>>> MultiSet([1, 2, 3]) - MultiSet([2, 3, 4])
Traceback (most recent call last):
...
ValueError: not enough occurrences``````
##### Call API
• `MultiSet other`: the multiset to substract
• `return MultiSet`
##### Exceptions
• `ValueError`: when the second multiset is not smaller

#### Method `MultiSet.__mul__`

``def __mul__ (self, other) :``

Multiplication by a non-negative integer.

``````>>> MultiSet([1, 2]) * 3 == MultiSet([1, 2] * 3)
True``````
##### Call API
• `non-negative`int other`: the integer to multiply
• `return MultiSet`
##### Exceptions
• `ValueError`: when `other` is negative

#### Method `MultiSet.__eq__`

``def __eq__ (self, other) :``

Test for equality.

``````>>> MultiSet([1, 2, 3]*2) == MultiSet([1, 2, 3]*2)
True
>>> MultiSet([1, 2, 3]) == MultiSet([1, 2, 3, 3])
False``````
##### Call API
• `MultiSet other`: the multiset to compare with
• `return bool`

#### Method `MultiSet.__ne__`

``def __ne__ (self, other) :``

Test for difference.

``````>>> MultiSet([1, 2, 3]*2) != MultiSet([1, 2, 3]*2)
False
>>> MultiSet([1, 2, 3]) != MultiSet([1, 2, 3, 3])
True``````
##### Call API
• `MultiSet other`: the multiset to compare with
• `return bool`

#### Method `MultiSet.__lt__`

``def __lt__ (self, other) :``

Test for strict inclusion. A multiset `A` is strictly included in a multiset `B` iff every element in `A` is also in `B` but less repetitions `A` than in `B`.

``````>>> MultiSet([1, 2, 3]) < MultiSet([1, 2, 3, 4])
True
>>> MultiSet([1, 2, 3]) < MultiSet([1, 2, 3, 3])
True
>>> MultiSet([1, 2, 3]) < MultiSet([1, 2, 3])
False
>>> MultiSet([1, 2, 3]) < MultiSet([1, 2])
False
>>> MultiSet([1, 2, 2]) < MultiSet([1, 2, 3, 4])
False``````
##### Call API
• `MultiSet other`: the multiset to compare with
• `return bool`

#### Method `MultiSet.__le__`

``def __le__ (self, other) :``

Test for inclusion.

``````>>> MultiSet([1, 2, 3]) <= MultiSet([1, 2, 3, 4])
True
>>> MultiSet([1, 2, 3]) <= MultiSet([1, 2, 3, 3])
True
>>> MultiSet([1, 2, 3]) <= MultiSet([1, 2, 3])
True
>>> MultiSet([1, 2, 3]) <= MultiSet([1, 2])
False
>>> MultiSet([1, 2, 2]) <= MultiSet([1, 2, 3, 4])
False``````
##### Call API
• `MultiSet other`: the multiset to compare with
• `return bool`

#### Method `MultiSet.__gt__`

``def __gt__ (self, other) :``

Test for strict inclusion.

``````>>> MultiSet([1, 2, 3, 4]) > MultiSet([1, 2, 3])
True
>>> MultiSet([1, 2, 3, 3]) > MultiSet([1, 2, 3])
True
>>> MultiSet([1, 2, 3]) > MultiSet([1, 2, 3])
False
>>> MultiSet([1, 2]) > MultiSet([1, 2, 3])
False
>>> MultiSet([1, 2, 3, 4]) > MultiSet([1, 2, 2])
False``````
##### Call API
• `MultiSet other`: the multiset to compare with
• `return bool`

#### Method `MultiSet.__ge__`

``def __ge__ (self, other) :``

Test for inclusion.

``````>>> MultiSet([1, 2, 3, 4]) >= MultiSet([1, 2, 3])
True
>>> MultiSet([1, 2, 3, 3]) >= MultiSet([1, 2, 3])
True
>>> MultiSet([1, 2, 3]) >= MultiSet([1, 2, 3])
True
>>> MultiSet([1, 2]) >= MultiSet([1, 2, 3])
False
>>> MultiSet([1, 2, 3, 4]) >= MultiSet([1, 2, 2])
False``````
##### Call API
• `MultiSet other`: the multiset to compare with
• `return bool`

#### Method `MultiSet.domain`

``def domain (self) :``

Return the domain of the multiset, that is, the set of elements that occurr at least once in the multiset.

``````>>> list(sorted((MultiSet([1, 2, 3, 4]) + MultiSet([1, 2, 3])).domain()))
[1, 2, 3, 4]``````
##### Call API
• `return set`: the set of values in the domain

### Class `Substitution`

``class Substitution (object) :``

Map names to values or names, equals the identity where not defined.

Substitutions support the `+` operation (union with consistency check between the two operands) and the `*` operation which is the composition of functions (`(f*g)(x)` is `f(g(x))`).

Several methods (eg, `image`) return lists instead of sets, this avoids the restriction of having only hashable values in a substitution image.

#### Method `Substitution.__init__`

``def __init__ (self, *largs, **dargs) :``

Initialise using a dictionnary as a mapping.

The expected arguments are any ones acceptables for initializing a dictionnary.

``````>>> Substitution()
Substitution()
>>> Substitution(x=1, y=2)
Substitution(...)
>>> Substitution([('x', 1), ('y', 2)])
Substitution(...)
>>> Substitution({'x': 1, 'y': 2})
Substitution(...)``````

#### Method `Substitution.__eq__`

``def __eq__ (self, other) :``

Test for equality.

``````>>> Substitution(x=1, y=2) == Substitution(y=2, x=1)
True
>>> Substitution(x=1, y=2) == Substitution(y=1, x=1)
False``````

#### Method `Substitution.__ne__`

``def __ne__ (self, other) :``

Test for inequality.

``````>>> Substitution(x=1, y=2) != Substitution(y=2, x=1)
False
>>> Substitution(x=1, y=2) != Substitution(y=1, x=1)
True``````

#### Method `Substitution.items`

``def items (self) :``

Return the list of pairs `(name, value)` such that the substitution maps each `name` to the correspondign `value`.

``````>>> Substitution(x=1, y=2).items()
[('...', ...), ('...', ...)]``````
##### Call API
• `return list`: a list of pairs (name, value) for each mapped name

#### Method `Substitution.domain`

``def domain (self) :``

Return the set of mapped names.

``````>>> list(sorted(Substitution(x=1, y=2).domain()))
['x', 'y']``````
##### Call API
• `return set`: the set of mapped names

#### Method `Substitution.image`

``def image (self) :``

Return the list of values associated to the names.

``````>>> list(sorted(Substitution(x=1, y=2).image()))
[1, 2]``````
##### Call API
• `return list`: the list of values associated to names

#### Method `Substitution.__contains__`

``def __contains__ (self, name) :``

Test if a name is mapped by the substitution.

``````>>> 'x' in Substitution(x=1, y=2)
True
>>> 'z' in Substitution(x=1, y=2)
False``````
##### Call API
• `str` (usually) name`: the name to test
• `return bool`: a Boolean indicating whether this name is in the domain or not

#### Method `Substitution.__iter__`

``def __iter__ (self) :``

Iterate over the mapped names.

``````>>> list(sorted(iter(Substitution(x=1, y=2))))
['x', 'y']``````
##### Call API
• `return generator`: an iterator over the domain of the substitution

#### Method `Substitution.__str__`

``def __str__ (self) :``

Return a compact string representation.

``````>>> str(Substitution(x=1, y=2))
'{... -> ..., ... -> ...}'``````
##### Call API
• `return str`: a simple string representation

#### Method `Substitution.__repr__`

``def __repr__ (self) :``

Return a string representation suitable for `eval`.

``````>>> repr(Substitution(x=1, y=2))
'Substitution(...)'``````
##### Call API
• `return str`: a precise string representation

#### Method `Substitution.dict`

``def dict (self) :``

Return the mapping as a dictionnary.

``````>>> Substitution(x=1, y=2).dict() == {'x': 1, 'y': 2}
True``````
##### Call API
• `return dict`: a dictionnary that does the same mapping as the substitution

#### Method `Substitution.copy`

``def copy (self) :``

Return a distinct copy of the mapping.

``````>>> s1 = Substitution(x=1, y=2)
>>> s2 = s1.copy()
>>> s1 == s2 and s1 is not s2
True``````
##### Call API
• `return Substitution`: a copy of the substitution

#### Method `Substitution.__setitem__`

``def __setitem__ (self, var, value) :``

Assign an entry to the substitution

``````>>> s = Substitution()
>>> s['x'] = 42
>>> s
Substitution(x=42)``````
##### Call API
• `str var`: the name of the variable
• `object value`: the value to which `var` is bound

#### Method `Substitution.__getitem__`

``def __getitem__ (self, var) :``

Return the mapped value.

``````>>> s = Substitution(x=1, y=2)
>>> s['x']
1
>>> try : s['z']
... except DomainError : print(sys.exc_info())
unbound variable 'z'``````
##### Call API
• `str` (usually) var`: the name of the variable
• `return object`: the value that `var` maps to
##### Exceptions
• `DomainError`: if `var` does not belong to the domain

#### Method `Substitution.__call__`

``def __call__ (self, var) :``

Return the mapped value or `var` itself if it is not mapped.

``````>>> s = Substitution(x=1, y=2)
>>> s('x')
1
>>> s('z')
'z'``````
##### Call API
• `str` (usually) var`: the name of the variable
• `return object`: the value that `var` maps to or `var` itself if it does not belong to the domain

#### Method `Substitution.__add__`

``def __add__ (self, other) :``

Add two substitution. Fails with `DomainError` if the two substitutions map a same name to different values.

``````>>> s = Substitution(x=1, y=2) + Substitution(y=2, z=3)
>>> s('x'), s('y'), s('z')
(1, 2, 3)
>>> try : Substitution(x=1, y=2) + Substitution(y=4, z=3)
... except DomainError : print(sys.exc_info())
conflict on 'y'``````
##### Call API
• `Substitution other`: another substitution
• `return Substitution`: the union of the substitutions
##### Exceptions
• `DomainError`: when a name is inconsistently mapped

#### Method `Substitution.__mul__`

``def __mul__ (self, other) :``

Compose two substitutions. The composition of `f` and `g` is such that `(f*g)(x)` is `f(g(x))`.

``````>>> f = Substitution(a=1, d=3, y=5)
>>> g = Substitution(b='d', c=2, e=4, y=6)
>>> h = f*g
>>> h('a'), h('b'), h('c'), h('d'), h('e'), h('y'), h('x')
(1, 3, 2, 3, 4, 6, 'x')``````
##### Call API
• `Substitution other`: another substitution
• `return Substitution`: the composition of the substitutions

#### Method `Substitution.restrict`

``def restrict (self, domain) :``

Restrict the substitution to `domain`, ie remove all elements that are not in `domain`. Note that `domain` may include names that are not in the substitution, they are simply ignored.

``````>>> s = Substitution(a=1, b=2, c=3, d=4).restrict(['a', 'b', 'z'])
>>> list(sorted(s.domain()))
['a', 'b']``````
##### Call API
• `iterable domain`: the new domain as a set/list/... of names
• `return Substitution`: the restricted substitution

### Class `Symbol`

``class Symbol (object) :``

A symbol that may be used as a constant

#### Method `Symbol.__init__`

``def __init__ (self, name, export=True) :``

If `export` is `True`, the created symbol is exported under its name. If `export` is `False`, no export is made. Finally, if `export` is a string, it specifies the name of the exported symbol. Exporting the name is made by adding it to the caller's global dict.

##### Call API
• `str name`: the name (or value of the symbol)
• `str` or `bool` or `None export`: the name under which the symbol is exported
``````>>> Symbol('foo')
Symbol('foo')
>>> foo
Symbol('foo')
>>> Symbol('egg', 'spam')
Symbol('egg', 'spam')
>>> spam
Symbol('egg', 'spam')
>>> Symbol('bar', False)
Symbol('bar', False)
>>> bar
Traceback (most recent call last):
...
NameError: ...``````

#### Method `Symbol.__eq__`

``def __eq__ (self, other) :``

Test for equality of two symbols, which is the equality of their names.

``````>>> Symbol('foo', 'bar') == Symbol('foo')
True
>>> Symbol('egg') == Symbol('spam')
False``````

#### Method `Symbol.__ne__`

``def __ne__ (self, other) :``

Test for inequality.

``````>>> Symbol('foo', 'bar') != Symbol('foo')
False
>>> Symbol('egg') != Symbol('spam')
True``````

#### Method `Symbol.__str__`

``def __str__ (self) :``

Short string representation

``````>>> str(Symbol('foo'))
'foo'``````

#### Method `Symbol.__repr__`

``def __repr__ (self) :``

String representation suitable for `eval`

``````>>> Symbol('foo')
Symbol('foo')
>>> Symbol('egg', 'spam')
Symbol('egg', 'spam')
>>> Symbol('bar', False)
Symbol('bar', False)``````