[Python-ideas] Trie ABC?

[Andrew Barnert]

On May 5, 2013, at 22:03, "Stephen J. Turnbull" <stephen at xemacs.org> wrote:

> Geoffrey Sneddon writes:
> 
>> Currently there are a large number of trie implementations for Python, 
>> all with slightly different APIs. It would be nice to introduce a ABC 
>> for Tries to attempt to unify these.
> 
> I don't understand why you want an ABC.  Mapping is the ABC, Trie is a
> concrete implementation, and an actual trie is an instance of Trie.

No, in his proposal, Trie adds new methods to the interface, on top of those required for Mapping (longest_prefix, etc.), making it an ABC.

> Wouldn't canonizing one of the existing implementations into the
> stdlib be the straight way forward?

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.

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?