fsharp/fsharpx — pull request #77 by supergrade (2012-06-30 19:54:23+00:00)
Title: Trie Map

3 distinct Trie maps, same API and general algorithm, all running the (haphazard/random-driven) unit test.

TrieMap_SS - Sparse, statically checked internalls (discriminated union)
TrieMap_PU - packed, untyped (nulls/typecasting) - uses bits to shrink the arrays
TrieMap_SU - sparse, untyped

Delete is included.

The "unit test" is barely that, it just fills it with a bunch of random keys (no-overwrite) then deletes them all again. It's enough to test a few cases; but not proven exhaustive through all the trees.

A key problem is performance. The typecasting or typechecking (explicit or implicit via the distriminated union in _SS), and various other safety checks (bounds checking on arrays) put the algorithm at a disadvantage.

This is currently much SLOWER than FSharp's Map.

It was easier to represent this in things like common lisp where you're coding to the low level; but I think to be practical need to be done in CLR or using some unsafe .Net or C# constructs that aren't in my toolbox.