Index  Comments

An upcoming program of mine will need a trie, as it's that most reasonable way to structure the data required of one stage in the processing. This is simple to do in Common Lisp, and the operations on a trie are few. Regardless, Common Lisp continues to be unsatisfying in this, for a litany reasons.

A major question in Lisp is how to structure data, and the CONS cell usually wins; I wrote a version of this library using CLOS instead, but it won me very little, and simply wasn't worthwhile. A trie has few operations, too few for CLOS to make much sense, and a CONS cell or two will be smaller than an object in memory, which is important when there will be many of them. The one advantage CLOS had was the unbound slot, for trie areas with no values, but this was solved by an additional CONS cell. Lastly, it's easy to read code manipulating lists, unlike objects with mostly customized operations.

Another negative aspect of CLOS is the printer, which I regard as a major design flaw of Lisp. With CONS cells, none of this be a concern; with CLOS, I would be required to either write the printer by myself, or go the easier route of ignoring it, with a much less usable trie resulting from such. My believing this to be a flaw stems from my general disgust with text, and from the issues apparent in Common Lisp: The printer has no sense of scale; corresponding reader issues must be placated; I view *PRINT-CIRCLE* to be a grotesque abomination; and there are many other reasons inappropriate to list here. Better languages will have no need to expose such a thing, and no need for any customization.

Unlike Ada, there's often no good way to get a constant-time operation for a finite domain in Common Lisp; with Ada, I may specify small and finite types and then construct further types which may only hold such values; with Lisp, I can technically get constant-time operations for such, but not in any satisfying way, only through mappings which look to be linear-time, even if not truly so; thus, it's usually easier to avoid such optimization, and allow such types to hold any manner of data possible.

The Common Lisp trie is sparse because of this, and I did notice an interesting optimization of that deletion function: Deletion may track a candidate node, a node with fewer than two children and with no value stored, in constant-space as it searches; the candidate node may then be removed wholesale, removing the entire branch, and the area around it cleaned; this is made simple by the sparse method making the children counting easy. However, I found this too difficult to implement correctly, even with decent effort given, and instead a far simpler, but correct, deletion function was implemented.

The Ada trie I've written is better in every way.

Here are the source and the license.