Collection library wish list

[rossberg]

The current Trie and Set provide fairly low-level interfaces whose use is not safe, e.g., because the user might accidentally mix multiple hash or eq functions. For a more complete picture, we should provide the following:

• functional unordered maps and sets (e.g. hash table)
• functional ordered maps and sets (e.g. red-black tree)
• imperative versions of the above (as wrappers where adequate)
• imperative dictionaries (i.e., maps over Text)

These should come with:

• "functor parameters" (ordering, hash functions) passed only to the constructor,
• iterators for keys, values, entries (key-value pairs),
• an object-oriented interface.

[matthewhammer]

@rossberg thanks for this list; LGTM.

I'll prioritize items from here during this month and next.

[matthewhammer]

Some things above (functional unordered maps) have been implemented, but not yet wrapped with a higher-level interface that avoids the programmer providing the hash function for each call.

Many things above are not implemented, though. None of them should be tricky, since they are all well-understood things (just not yet expressed in Motoko).

I have a rough dependency order in mind:

Imperative hash table:

• User-provided hash function, via the class/constructor idiom
• Growable arrays (aka RamBuf in #865)
• Association lists (done already)

Based on these ingredients, a simple hash table should be routine to implement in Motoko.

Red-black trees:

For the purely-functional version, I would follow my notes of the Okaski treatment of these. I taught them at some point recently (to undergrads, in Elm), so it shouldn't be hard to reproduce in Motoko.

Wrappers / Iterators

I think I can envision the wrappers and iterators mentioned above, though I need to work each out to be sure of the details.

[kritzcreek]

I think we've got all those data structures in base now. Can we close this @matthewhammer?