In Lisp, should lists be replaced with trees?

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.

Introduction

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).

Rationale

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:
  • 'The Universal Design Pattern'

Sketch

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>])

Conclusion

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