I would like to share some thoughts about a specific limitation of the Wolfram Language and ask for ideas about how problems of the sort I'll describe below could be handled better.
Mathematica has many functions for discrete mathematics. A common feature of combinatorial objects is that their numbers tends to explode as they get larger. Think e.g Tuples[Range[n], k]
there are
$n^k$ of them.
Because of this problem, functions that can return all solutions to some combinatorial problem usually take an argument that limits the number of results. Take e.g. FindCycle
or FindClique
. They can find at most
$n$ cycles/cliques.
But this approach comes with a big limitation: what if I already generated 1000 cliques, but then I realize that I need the 1001st one as well? There is no way to continue the clique generation process. The only option I have is to start from scratch.
Languages like Python use the concept of iterators for this. First, we set up an iterator object, e.g. an iterator of cliques of a given graph. Then we request the first result. We can process it as we like. If we need another result, we can request it too, and so on. It is up to the iterator's user to decide how many results to request, and when to discard the iterator data structure.
Not only can Mathematica not do this, I don't even see how something like this could be efficiently incorporated into the language. Iterators are, by nature, mutable objects. Mutability does not fit into the Wolfram Language well.
In fact, the incremental generation of such objects is so useful, that it is included in some parts of Mathematica too:
The 3rd argument of Subsets
allows us to request the k
th subset. This approach works for subsets because it is easy to directly generate the k
th one, without first creating the first k-1
st ones. For harder combinatorial problems, this is not going to be possible.
Prime
appears to work the same way as Subsets
: Prime[k]
appears to directly give the k
th prime. But notice that Prime[k+1]
evaluates much faster if Prime[k]
has already been computed. Mathematica does in fact maintain some internal state while computing primes, and makes use of it for later computations, just like an "iterator object" would. However, unlike in the case of an iterator object in Python, we have no access to this state. We can't save it, and re-load it in a later session.
Please consider this as a feature request or a suggestion. I am asking to change the paradigm for generating combinatorial objects (of which there may be lots, more than what fits in memory) in the Wolfram Language. While the Wolfram Language does not seem to make it possible for users to implement an efficient iterator, I am sure that it could be done as a built-in, atomic expression.
For a concrete example of how iterators can be used for combinatorial work, see DegreeSequences in SageMath.
I hope I managed to make a good case for why iterators are important for a system that can do discrete mathematics. Any thoughts from other users?