3 ms·
> "Lists, which are a generalization of graphs, are extraordinarily well supported by Lisp." I always thought of linked lists as a special kind of graph, where
by arknave 8y ago
> "Lists, which are a generalization of graphs, are extraordinarily well supported by Lisp."
I always thought of linked lists as a special kind of graph, where each node except the head and tail had exactly one incoming edge and one outgoing edge. What's a better way to think of this in terms of LISP?
- mirekrusin 8y agoAn array of bits is generalisation of everything.
- thaumasiotes 8y agoInternally a Lisp list is a binary tree in which left children are leaves storing a value and right children aren't leaves (except the terminus) and don't store values. Or rather, there is a structure called a cons cell which consists of two pointers, "left" and "right"; a cons cell in which the right pointer is NIL is a list; and a cons cell in which the right pointer points to a list is also a list. The values in the list are whatever is pointed to by the left pointers. If you diagram this out, you'll find that your mental image is basically accurate already. It seems difficult to describe lists of this form as a "generalization" of graphs.