# Checking equality of self-referential lists

Define that an srlist ("self-referential list") over $$X$$ consists of a list of elements of $$X \sqcup \mathrm{srlist}(X).$$ So basically, the items can be primitive values, or further self-referential lists, or a mixture of both. Cycles are allowed.

For example, $$S = [S]$$ is a perfectly good definition of an srlist. Define two srlists to be equal if and only if the possibly infinite tree that the srlist represents are equal. For example, observe that $$S$$ looks a bit like this:

$$* \rightarrow * \rightarrow * \rightarrow \,...$$

So too does the srlist defined by $$T = [T]$$. Hence $$T = S$$. In a similar way, if we define $$U = [[U]]$$, the resulting infinite tree will look the same as above. So $$U = S$$.

Question. I'm trying to find an algorithm for checking equality of srlists, but unfortunately the naive approach of using recursion has issues with never halting for most srlists, due to the possibility of cycles. Ideas, anyone?

• How are the lists given to the algorithm? As pointers? Can we test for equality of pointers? Oct 21, 2023 at 8:23
• @AndrejBauer, yep, they're pointers. So the function of interest is given two srlist pointer, and each of those srlists consists of a contiguous block of memory whose first item stores the length of that block and whose remaining items are either srlist-pointers, or else raw data. We can tell raw data and srlist-pointers apart from each other in $O(1)$ time, and we can test for pointer equality in $O(1)$ time. Oct 22, 2023 at 11:32

We define the signature of an srlist $$S$$ as the set of finite sequences $$a_i$$ of integers such that $$S[a_1][a_2][a_3]...[a_n]$$ exists. It's not hard to see that two srlists are equal iff the have the same signature.
It's also not hard to see that the signature of an srlist is a regular language - the states are all values in $$S$$, recursively, but without following references, and the transitions are obvious.
So you can convert $$S$$ and $$T$$ to their finite automata and test for their equality.
If you want to support primitive types you can have $$S[a_1][a_2]...[a_{n-1}] = a_n$$ as a signature instead, and allow $$S[a_1][a_2]...[a_{n-1}] = *$$ if it's a list (to still test the list structure if it's infinite).