Tag: informal methods

What’s a tree? First define a sequence or length n> 0 as a total map s: {1,.. n}→ X. Let Nil be the empty sequence.  If s is a sequence of length n, and x is an element, then u = sx is the sequence of length n+1 so that u(n)=x and for i < n, u(i)=s(i). That is sx is the sequence obtained by appending element x to sequence s on the right. If X is a set, let X* be the set of finite sequences over X, the minimal set that includes Nil and sx so that if s is an element of X*, sx is also an element. If s is a sequence, then either s=Nil or s = ux for some sequence u that has a length one less than the length of s. Define the predecessor of a sequence by Pred(Nil)=Nil and Pred(ux)=u.

A tree is a map  T: X* → Y where whenever T(s) is defined, T(Pred(s)) must be defined. Note that T(Nil) must be defined if T is defined on any elements of X* at all.

Let V  the set of vertices contain exactly those elements s of X* so that T(s) is defined.  If V is not empty, Nil is in V and call Nil the  “root”. Let E the set of labeled edges consist of exactly all triples (s,x,sx) where T(sx) is defined. Then (V,E) is the standard graph theoretic definition of a tree.  Suppose, on the contrary that (V,E) is a tree with labeled edges, that is it is a undirected graph that is connected but has no cycles. Then define T(Nil) = root and T(sx) = v s.t. there is an edge labeled x from T(s) to v.

So a sequence is a map from numbers to elements and a tree is a map from sequences to elements.

What’s a linked list?

1.  Let V be a set of values and A be a set of “addresses”.
2. Say a map f is a “linked list element” compatible with values V  and addresses A if and only if f(value)∈ V and f(next) ∈  A. A linked list element map can have an arbitrary additional domain – we don’t specify that here.
3. Let L: A→ X where X is a set of  linked list elements compatible with V and A.  L associates addresses with linked list elements.
4. Given any a ∈ A we want to be able to trace the linked list with “a” as the head element. Define E(L,a,0) = a and  E(L,a,n+1) = (L(E(L,a,n)))(next).  The expression (L(E(L,a,n)))(next) can be unwrapped to understand it better (L(E(L,a,n)))(next) = (L(a’))(next) where E(L,a,n) = a’. Then (L(a))(next) = f(next) where L(a)=f is a linked list element. So the final value is some a”, an element of A.
5. Say (L,a) is a linked list iff for every element a’∈A s.t. L(a’) is defined,  there is some non-negative n so that E(L,a,n) = a’
6. Say (L,a) is a circular linked list iff it is a linked list and for some n, E(L,a,n+1) = a.

Finite sequences of length n>0 can be represented mathematically as maps u:{0, … n-1}→ Y for some set Y.   If  (L,a) is a circular linked list, define u(0) = L(a)(value) and  u(n+1) =  L(E(L,a,n+1))  if E(L,a,n+1)=  a, and undefined otherwise.