In Lisp, should lists be replaced with trees?

NOTE HXA7241 2011-05-15T09:07Z

Conses/pairs/lists are rather low-level when you think about it. Would we not appreciate something just a little more powerful, a little more modern? A tree primitive is here casually and heretically proposed as a better alternative.

MJS prompted reconsidering Lisp's core compound data-structuring element, conses/lists. The main point was roughly that conses/lists are too crude, and too concrete (although their typing weakness will not be addressed here).

So, first a view of why and how they are overly primitive. Then a sketch of a reasonable possible replacement idea (as Scheme).


Conses/lists seem like a mismatch in the language. They are more rudimentary than they should be compared to their context. They are also a little weak compared to common programming equivalents.

The grounds of the opinion is a sense of data-structure/algorithm symmetry – that the basic algorithmic means should balance with the basic data-structuring means. This is not very well-founded, it just has an immediately reasonable appeal.

Seemingly, conses/lists presume to be the lambda of data structures. Do they merit that position? Yes they do, in a way, But the problem is that is not what we want. They should really be equivalent to procedures/functions, which are a notch more developed for programming than lambdas.

Lambdas, in lambda-calculus world, assemble in a currying way: they do not have parameter lists, but chain calls of single parameters. This matches conses/lists.

But Lisp does not really have lambdas, it has procedures/functions – calls are not currying and parameters are arrays, each addressed by name. So, to match, Lisp should not have conses/lists, but instead the slightly higher level equivalent to procedures: dictionary-trees. A ‘dictionary-tree’ being: a tree-like structure, with items at each node addressed by name – like a JavaScript/Lua object.

  • Lists are like lambdas, not procedures:
    • a simple sequence of elements linked together.
  • The data equivalent of procedures is dictionary-trees:
    • procedure structure is hierarchical – hence tree,
    • procedure parameters are named – hence dictionary.
  • And the current/average/popular/pragmatic/core/basic data-structure is probably the JavaScript/Lua-style object/table/associative-array:

Replace ’pair’ (in Scheme) with an alternative data structuring building-block, ’branch’:

  • branch
    • item – name-value association
    • item – name-value association
    • item – name-value association
    • . . .

This is like pair except generalised and easified:

  • any number of items (zero or more), instead of just two,
  • and each item is named (and indexed?).

And this generalised structure is simpler than pair: pair's having two items is like a special constant, ad hoc (but for what good reason now?).

Branchs/trees are a superset of pairs/lists, so could straightforwardly support all list operations. A pair is just a branch with two items, named ‘car’ and ‘cdr’. Nil is perhaps redundant, since the tail end of a list could simply have only one item. But nil can be explicitly represented by a branch with zero items.

Operations on branchs/trees can be quite easily adapted from Scheme's operations on pairs/lists:

  • Type predicates:
    • (branch? <arg>)
    • (tree? <arg>) – is not some other graph shape
    • (null? <arg>) – is zero-size branch
  • Constructors:
    • (branch [(name-value <name> <value>) ...]) – like cons and list
    • (append <branch> (name-value <name> <value>) ...) – add at leaf end
    • (reverse <branch>) – reverse branch (index) ordering
      • recursive ?
  • Queries:
    • (item <branch> <name|index> [<name|index> ...]) – read a value, optionally recursively
    • (branch-size <branch>) – item count (not including branchs?)
    • (tree-size <branch>) – recursive
    • assoc ops are redundant, since items are named anyway
    • find matching item
      • . . .
    • comprehensions
      • hierarchical/tree equivalents of: map, fold, filter, unfold, . . .
  • Commands:
    • (item-set! <branch> <name|index> <value>)
    • (item-add! <branch> <name|index> <value>)
    • (item-del! <branch> <name|index>)
  • Conversions:
    • (tree->vector <branch> [<order>])

It is not entirely convincing, yet there is something to it. (And of course, it would no longer be Lisp: it would be Trep.)