Domains¶
This section introduces the core structure of Haydi: domains and basic operations with them. Advanced domains and canonical forms are covered in a separate section: Canonical forms.
Elementary Domains¶
One of basic structures in Haydi is Domain
that represents a generic
collection of arbitrary objects. The main operation with domains is to provide a
method for iteration and random generation of elements in domain. Domains are
composable, i.e. more complex domains can be created from the simpler ones.
There are six elementary domains shipped with Haydi: Range
(range of
integers), Values
(domain of explicitly listed Python objects),
Boolean
(two-element domain), and NoneDomain
(a domain
containing only one element: None
), USet
, and CnfValues
.
Domains USet
and CnfValues
are little bit special and they are
designed for enumerating non-isomorphic structures. The topic is covered in
Canonical forms; these domains are not used in this section.
Examples:
>>> import haydi as hd
>>> hd.Range(4) # Domain of four integers
<Range size=4 {0, 1, 2, 3}>
>>> hd.Values(["Haystack", "diver"])
<Values size=2 {'Haystack', 'diver'}>
>>> hd.Boolean()
<Boolean size=2 {False, True}>
>>> hd.NoneDomain()
<NoneDomain size=1 {None}>
Composition¶
New domains can be created by composing existing ones. There are the following compositions: product, sequences, subsets, mappings, and join.
Cartesian product \((A \times B)\)¶
Product
creates a domain of all ordered tuples; for example:
>>> import haydi as hd
>>> a = hd.Range(2)
>>> b = hd.Values(("a", "b", "c"))
>>> hd.Product((a, b))
<Product size=6 {(0, 'a'), (0, 'b'), (0, 'c'), (1, 'a'), ...}>
alternatively, the same thing can be written by using the infix operator *
:
>>> a * b
<Product size=6 {(0, 'a'), (0, 'b'), (0, 'c'), (1, 'a'), ...}>
The product can be created on more than two domains:
>>> hd.Product((a, b, hd.Values["x", "y"]))
<Product size=12{(0, 'a', 'x'), (0, 'a', 'y'), (0, 'b', 'x'), ...}>
>>> a * b * hd.Values(["x", "y"])
<Product size=12{(0, 'a', 'x'), (0, 'a', 'y'), (0, 'b', 'x'), ...}>
Note
Generally, a * b
equals to hd.Product((a, b))
. However, there is one
exception when a
is also product. The expression hd.Product((x, y)) *
b
is equal to hd.Product((x, y, b))
(not hd.Product(hd.Product(x, y),
b)
). The reason is to enable definining n-ary tuples by multiplication. If
you want to avoid this behavior and define “product in product”, then
explicitly use hd.Product
instead of *
.
Sequences \((A^n)\)¶
Sequences
is a shortcut for a product over the same domain.
Sequences of a given length can be defined as:
>>> import haydi as hd
>>> a = hd.Range(2)
>>> hd.Sequences(a, 3) # Sequences of length 3
<Sequences size=8 {(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), ...}>
or sequences with a length in a given range:
>>> hd.Sequences(a, 0, 2) # Sequences of length 0 to 2
<Sequences size=7 {(), (0,), (1,), (0, 0), ...}>
Sequences of a fixed length can also be created by the ** operator on a domain:
>>> hd.Range(2) ** 3
<Sequences size=8 {(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), ...>
Subsets \((\mathcal{P}(A))\)¶
The Subsets
contains subsets from elements of a given domain;
the following example creates the power set:
>>> import haydi as hd
>>> hd.Subsets(hd.Range(2))
<Subsets size=4 {{}, {0}, {0, 1}, {1}}>
When a single argument is provided, it is used to limit subsets to a given size:
>>> hd.Subsets(hd.Range(3), 2) # Subsets of size 2
<Subsets size=3 {{0, 1}, {0, 2}, {1, 2}}>
Two arguments limit the subsets to a size in a given range:
>>> hd.Subsets(hd.Range(3), 0, 1) # Subsets of size between 0 and 1
<Subsets size=4 {{}, {0}, {1}, {2}}>
Note
Type of elements created by Subsets
is not the standard Python
set
, but haydi.Set
. For more information, see Set and Map.
This behavior can be overridden by argument set_class
:
>>> hd.Subsets(hd.Range(2), set_class=frozenset)
<Subsets size=4 {frozenset([]), frozenset([0]), frozenset([0, 1]), ...}>
Mappings \((A \rightarrow B)\)¶
The domain Mappings
contains all mappings from a domain to another
domain:
>>> import haydi as hd
>>> a = hd.Range(2)
>>> b = hd.Values(["a", "b"])
>>> hd.Mappings(a, b)
<Mappings size=4 {{0: 'a'; 1: 'a'}, {0: 'a'; 1: 'b'}, {0: ... a'}, ...}>
Note
Type of elements created by Mappings
is not the standard Python
dict
, but haydi.Map
. For more information, see Set and Map.
This behavior can be overridden by argument map_class
:
>>> hd.Mappings(a, b, map_class=dict)
<Mappings size=4 {{0: 'a', 1: 'a'}, {0: 'a', 1: 'b'}, {0: ... a'}, ...}>
Join \((A \uplus B)\)¶
Join
operation creates a new domain that contains elements of all given
domains (disjoint union):
>>> import haydi as hd
>>> a = hd.Range(2)
>>> b = hd.Values(["abc", "ikl", "xyz"])
>>> c = hd.Values([123])
>>> hd.Join((a, b, c))
<Join size=6 {0, 1, 'abc', 'ikl', ...}>
The same behavior can be also achieved by + operator on domains:
>>> a + b + c
<Join size=6 {0, 1, 'abc', 'ikl', ...}>
Note that Join
does not collapse the same elements in the joined
domains:
>>> a = hd.Range(2)
>>> b = hd.Range(3)
>>> a + b
<Join size=5 {0, 1, 0, 1, 2}>
Let us make now a small detour: Each domain can create a random element by
calling generate_one()
:
>>> a = hd.Range(2)
>>> b = hd.Values(["abc", "ikl", "xyz"])
>>> c = hd.Values([123])
>>> d = a + b + c
>>> d.generate_one()
"ikl"
By default, domains return each element with the same probability and
Join
is not an exception. Therefore, each element of d
has
probablity 1/6 to be returned by generate_one()
(d
has six elements).
This can be changed by ratios
argument:
>>> d2 = hd.Join((a, b, c), ratios=(1, 1, 1))
First, we choose with the same probability (1:1:1) from which subdomain we want
to pick an element and generate_one()
is called on the selected domain.
Therefore 123 will occur with probability 1/3; “ikl” has probability 1/9.
Laziness of domains¶
A domain is generally a lazy object that does not eagerly construct its elements. Therefore if we use code like this:
>>> import haydi as hd
>>> a = hd.Range(1000000)
>>> a * a * a
<Product size=1000000000000000000 {(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), ...}>
we obtain the result instantly, it only instantiates first few objects for the repr string. The ways how to instantiate elements from a domain is explained in Pipeline.
Transformations¶
Another way of creating new domains is applying a transformation on an existing domain. There are two basic transformations: map and filter.
Map¶
Map transformation takes elements of a domain and applies a function to each element to create a new domain:
>>> a = hd.Range(4).map(lambda x: x * 10)
>>> a
<MapTransformation size=4 {0, 10, 20, 30}>
The resulting object is again a domain. For example we can make a product of it:
>>> a * a
<Product size=16 {(0, 0), (0, 10), (0, 20), (0, 30), ...}>
Filter¶
Filter transformation creates a new domain by removing some elements from an existing domain. What elements are removed is configured by providing a function that is called for each element and should return True/False. When the function returns True, then the element is put into the new domain.
>>> hd.Range(10).filter(lambda x: x % 2 == 0 and x > 5)
<FilterTransformation size=10 filtered>
As we can see, the returned repr string is a different from what we have seen so far. The flag ‘filtered’ means that domain contains a filter transformation and the size argument is not exact but only an upper bound. The reason is that to obtain a real size we need to apply the filter function to each element (which would require going through a potentially very large domain).
If we transform the domain into the list, we force the evaluation of the domain and obtain:
>>> list(a)
[6, 8]
The ‘filtered’ flag is propaged during the composition of domains. When a domain is created by composing at least one filtered domain, it is also filtered:
>>> p = a * a
<Product size=100 filtered>
Names¶
It is possible to provide a name for a domain as an argument in the domain constructor. This name serves only for debugging purposes. For example:
>>> import haydi as hd
>>> a = hd.Range(10, name="MyRange")
>>> a
<MyRange size=10 {0, 1, 2, 3, ...}>
>>> a.name
'MyRange'
>>> a = hd.Range(10)
>>> hd.Product((a, a), name="MyProduct")
<MyProduct size=100 {(0, 0), (0, 1), (0, 2), (0, 3), ...}>