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 trivial to do in Ada using a limited private type, and then the few operations available are total. The only unsatisfying aspects are the deallocation of nodes and storing multiple values in one place, but both can be circumvented or ignored for this.

In Ada, I may structure data however I prefer, and it's due to this that I'm entirely satisfied with my design. Every aspect of this design is pretty; each instantiated type and subprogram is named by a four-letter word. The lack of deallocation would be an issue, but the Sift subprogram gets in the way of that anyway; the nature of the limited type does mean it would be particularly easy to manage nodes individually. That Boolean value of each node would be a waste if a list type were to be used to store multiple values in one place, but this is relatively unimportant, and not currently needed.

There's no subprogram to represent the trie textually, but also none is needed, or even wanted.

The Lisp version may store any value along the trie, and use any equality test in its searching, but neither of these are necessary for the majority of programs using a trie; with Ada, an array is used and so requires a discrete type, but this gives predictability in storage and access; often, but one equality test be needed, the natural equality, and this is effortless by the nature of array access.

The Give, Take, and Find subprograms are self-explanatory; only Sift needs an explanation. The Sift is a version of Find which returns the trie node itself, and is primarily useful in caching a search or implementing the other subprograms. I considered giving that first trie parameter of Sift a mode of in out, but that would make it too easy to misuse and lose part of the trie permanently; a second parameter with a mode of out is used for any result, thus. I also considered giving that first trie parameter such a mode, purely to have the aliasing rules prevent overwriting the input trie's value, but decided against this, as the separate parameters already make this unlikely and any such mistake likely intended. It's not impossible to misuse, but is as good as is reasonable for a trivial trie.

Here are the package specification, the package body, and the license.