[Python-ideas] Trie ABC?

[Stephen J. Turnbull]

Andrew Barnert writes:

 > Even if we did, is it conceivable that someone might want to use
 > another implementation, or an extension to the concept, or a
 > wrapper, and want to signify that it implements a Trie, in the same
 > way we can with MutableMapping (and all the other ABCs)? I'm not
 > actually sure, but it's not something to dismiss out of hand.

I asked precisely because I'm not dismissing it.  If I really thought
it were dismissible, I'd just let somebody authoritative do so.

 > Put another way: we canonized a set implementation, and that didn't
 > mean we had no use for a Set ABC. Why is Trie inherently different?

It's not *inherently* so.  As you point out, the additional methods
needed make it implicitly a different ABC from Mapping.  But it's also
not clear to me that it's not different from Set, that we can't do
well enough with a single implementation that is well-optimized.  We
don't need a Sorter ABC; timsort is good enough for practical
purposes.  Maybe that's the way tries are, too.  I'd like to hear more
about it.