I would like to model linked lists using set theory similar to that in Scheme and LISP.

There is a set theoretic definition of the ordered pair:

$p = \{\{a, 1\}, \{b, 2\}\}$

My question is how does one distinguish a value from a pointer to another list? Should I just use more types like $3$ for value and $4$ for pointer?

So in LISP:

$l= ((('a').()), (('c'.'d').()))$

In set theory beginning of above list:

$l = \{\{h, 1\}, \{i, 2\}\}$

$h = \{\{a, 1\}\}$

$a = \{\{b, 4\}\}$

$b = \{\{'a', 3\}\}$

Without distinguishing pointer from value I'm not sure how a distinction can be made.


1 Answer 1


Now that you have defined ordered pairs, you can do what LISP does: $\operatorname{NIL}$ is a list and if you have a list $l = (a, b)$ then $a$ is a value and $b$ is a list. Of course, lists can be used as value themselves.

For example, the list $(a.b.c)$ is defined to be the ordered pair $(a, (b, (c, \operatorname{NIL})))$.

Thus $$l = ((('a') . ()) . (('c' . 'd'). ()) = (x_1, (y_1, \operatorname{NIL}))$$ where : $$x_1 = (('a') . ()) = (x_2, NIL)$$ $$x_2 = ('a', \operatorname{NIL})$$ $$y_1 = (('c' . 'd') . ()) = (y_2, (\operatorname{NIL}, \operatorname{NIL}))$$ $$y_2 = (c . d) = ('c', ('d', \operatorname{NIL}))$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.