# Acyclic lists and innumerable trees

Is it possible to express infinite and even uncountable sets in a programming language? If it is, what good can it do?

Infinite strings, trees and sequences seem like useless things. It takes enormously long time to compute them, or to print or compare them. However, in many situations a particular application examines only a finite subset of a potentially infinite structure. Alas, often one can't tell in advance how big this subset is: therefore, one can't simply precompute it. It doesn't mean though that we have to compute the whole infinite structure and then hand it over to the application. We only need to make a "next" element available whenever the application asks for one. Lazy computation is such a remarkable invention indeed. Furthermore, sometimes we can manipulate infinities "symbolically" by operating on their generating functions.

This article initially aimed to give an example of a list that is neither proper nor improper nor cyclic. The example was later extended to the construction of an infinite tree. This stirred up a long discussion: whether the number of leaves in the tree is countable, whether constructive reals can be effectively enumerated, and if it makes sense to talk about (uncountable) infinities in the constructive context of computer programming. Incidentally, the infinite tree `bb` that spawned the thread turned out to be a model of surreal numbers.

Cantor would have had fun with Scheme. I wonder if someone uses Scheme to teach or research in set theory or modern algebra.

The present page is a compilation of several articles posted on comp.lang.scheme, comp.lang.functional newsgroups Sep 22 through Oct 6, 1999.

## Pathological lists

Lists are commonly classified [SRFI-1] into three disjoint sets:

• Proper lists: finite, nil-terminated lists
• Improper: finite, non-nil-terminated lists
• Circular lists. "A circular list is a value such that for every `n >= 0`, `cdrn(x)` is a pair."
I'm afraid I have stumbled on a pathological case, which does not appear to fit either category.

As R5RS, Ch 6.4 specifies, "Some implementations may implement 'implicit forcing,' where the value of a promise is forced by primitive procedures like `cdr` and `+`". Let us assume such an implementation and consider:

```(define (succ n)
(cons n (delay (succ (+ 1 n)))))

; this is, btw, the n-th Church numeral
(define (n-times n f x)
(let loop ((n n) (x x))
(if (positive? n) (loop (- n 1) (f x)) x)))

(define b (succ 1))
```
Note, that `(n-times n cdr b)` is always a pair, for any `n`. Thus `b` cannot be a dotted list. It can't be a proper list either as `(n-times n cdr b)` is never `'()`. Finally, it is easy to see that
`(car (n-times n cdr b)) ==> n+1`
for any `n`. Therefore, `(equal? (list-ref b n) (list-ref b m))` is `#f` for any `n` not equal `m`. It seems inappropriate to call list `b` cyclic as it has no cycles.

## An infinite spreading tree `bb`

As even more interesting case, consider

```(define (succsucc n)
(cons (delay (succsucc (* 2 n)))
(delay (succsucc (+ 1 (* 2 n))))))

(define bb (succsucc 0))
```
It represents an infinite full binary tree spreading out in both dimensions.

## Why the tree `bb` represents an uncountable set (continuum)

### Isomorphism to a set of all binary strings

By construction, the tree `bb` is isomorphic to a set of all binary strings (including the infinite ones), modulo disregarding trailing zeros as usual. This set obviously has the cardinality of `2^c0`, and is uncountable.

### Reply to a counter-argument: "there are never actual elements"

One article in a discussion thread for the tree `bb` posed a counter-argument:

That is, it's an infinite loop. Well, of sorts. One does get a tree of promises, but each promise only makes more promises. There are never any actual value elements.

Nevertheless, one can define an isomorphism between the tree `bb` and a set of all binary strings in the following way: Consider a path in the tree starting at the root and never ending. It corresponds to one particular binary string. If the string is finite, the path ends with an infinite sequence of "zeros" (read: left edges or nodes, or `car`s). Infinite binary strings correspond to other paths. It appears that there is a path for each binary string, and there is a binary string for any path. Hence the isomorphism. The set of all binary strings is known to be uncountable.

In the above derivation, the fact that tree nodes (`cons` cells) have no values is irrelevant. What's important is that every node has the left and the right child, and they are different (not `eq?`).

### Can all the paths be indexed? No, by a diagonal slash

The discussion thread presented arguments concerning the possibility of indexing all paths in the tree `bb`. For example:

Perhaps you mean:
``` (define (succsucc1 n)
(cons (if (odd? n) 1 0)
(cons (delay (succsucc1 (* 2 n)))
(delay (succsucc1 (+ 1 (* 2 n)))))))
(define bb1 (succsucc1 0))
```
It is countable, however. Each implied binary string can be thought of as a binary integer, which is its index.
Let's consider this tree truncated at depth `d`. Obviously there are `2^d` distinct paths in this tree that start at the root and end at a leaf -- just as there are `2^d` leaves. Each path (leaf) has a binary string associated with it. To enumerate all paths/leaves, we need `2^d` numbers. If we increase the depth by 1, we have to double the quantity of numbers to enumerate paths/leaves. If `d` increases to infinity (`c0`), we "run out" of numbers to assign to every path...

Every path in trees `bb` or `bb1` of a finite length can be enumerated. The question is: can we count all the infinite paths from the root? A diagonal slash argument makes it clear that one cannot assign a natural number to every infinite path in `bb`.

### Confusion between nodes and paths

The conclusion of the innumerability of paths in the tree `bb` may be puzzling and frequently leads to a confusion because the number of nodes in the tree is indeed countable.

It is important however to draw a distinction between nodes and paths. In a finite tree, these two are equivalent. The set of paths is isomorphic to the set of nodes (this can be taken as the definition of a tree as a prefix-complete set of paths). Indeed, in a finite tree, each path from a root ends at some node, and for each node there is a unique path from the root (or any other node).

An infinite tree, such as the tree `bb`, admits infinite paths, for example, `left, right, left, right, ....`. Each node in `bb` has the left neighbor and the right neighbor. There is always a possibility to go left or right, from any place. The tree admits many other infinite paths, e.g., ```left, left, right, left, left, right, ...``` or the paths with the sequence of 'left' and 'right' induced by the binary representation of `PI`. In an infinite tree, the isomorphism of nodes and paths no longer holds: there are infinite paths in the tree that do not end at all. Consider a set of numbers in [0,1] expressed as infinite decimal fractional sequences. If we limit the decimal sequences to some length, their set is countable. Indeed, if we truncate the decimal representation of a number we get a rational number, and the set of rational numbers is countable. If we allow arbitrary infinite decimal expansions, the set of such numbers become uncountable. The extra size comes from the numbers that correspond to the expansion that continue forever without any regular pattern.

It is easy to see and prove that for each (finite or infinite) binary string, the tree in question contains the corresponding path. Because the set of all binary strings is uncountable, so is the set of the paths admitted by the tree. The tree `bb` is not only infinite, it is irregular.

### Last updated October 1, 2006

This site's top page is http://okmij.org/ftp/
oleg-at-okmij.org