Paul LaFollette paul.lafollette at gmail.com
Sun Jun 14 18:49:56 CEST 2009

```Thank you all for your thoughtful and useful comments.  Since this has
largely morphed into a discussion of my 3rd question, perhaps it would
interest you to hear my reason for asking it.

John is just about spot on. Part of my research involves the
enumeration and generation of various combinatorial objects using what
are called "loopless" or "constant time" algorithms.  (This means that
the time required to move from one object to the next is bounded by a
constant that is independent of the size of the object.  It is related
to following idea:  If I generate all of the possible patterns
expressible with N bits by simply counting in binary, as many as N
bits may change from one pattern to the next.  On the other hand if I
use Gray code only one bit changes from each pattern to the next.  If
you are interested in this essentially useless (but fun) subject, the
seminal paper by Gideon Ehrlich is here:
http://portal.acm.org/citation.cfm?id=321781 )

Now, suppose that I want to generate, say, the set of all ordered
trees with N nodes.   I need to be able to represent the empty ordered
tree, i.e. the tree with with zero nodes.  There are a lot of ways I
could do this.  The problem is that I might tomorrow be looking
instead at rooted trees, or free trees, or Young tableaux and in each
case I will need to represent the empty rooted tree, or the empty free
tree, or the empty Young tableau.

In a very real sense, the empty Young tableau IS a Young tableau and
the empty ordered tree IS an ordered tree.  But in an equally real
sense they are the same "ghost of a thing" looked at in different
universes of discourse.

So, what I would like is some sort of object that is a "kind of"
everything but contains nothing, a unique minimal element of the
partial ordering imposed on the set of classes by the inheritance
heierarchy.  Whilst I am not naive mathematically, I am relatively
naive in the area of language design.  In my naivete, it seemed to me
that None could have been designed to be such a thing.  Apparently
that is incorrect.

The matter is not urgent, there are oodles of workarounds.  Indeed,
having once found a particular loopless algorithm I don't necessarily
publish an implementation of it, but rather a formal description and
proof of correctness.  Still, before I submit things for publication I
generally prefer to implement them for myself just to convince myself
that what I have proved correct in fact works at least for modest
values of N.

Paul
____________________________________
paul[dot]lafollette[at]gmail.com
http://www.cis.temple.edu/~lafollet

```