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([[], [1]]))
[]
```
##### 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()))
[2]
```
##### 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([1])
>>> 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()[1])
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()[1])
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)
```