[Python-ideas] Trie ABC?

[Andrew Barnert]

From: Geoffrey Sneddon <foolistbar at googlemail.com>

Sent: Tuesday, May 7, 2013 11:03 AM


> But yes: I think Andrew has succulently explained why I'm not rushing into 
> trying to push a specific implementation into the stdlib. I'm not against 
> putting one in, but it'll need to be carefully chosen: any pure-Python one 
> will likely have undesirable memory usage due to the overhead per string object 
> (there's a reason for my implementation implements the interface using a 
> binary-search-tree and not a trie!); and most modern C implementations are 
> separate libraries: the Python wrapper is only really interesting from an API 
> POV, so it doesn't matter too much if we choose something not used before.


That raises another interesting point: The same implementation can support both a Trie interface and a SortedMapping interface (or, for that matter, both SortedMapping and Heap)—but not _every_ implementation can, or should.

Which is a good argument for having both ABCs in the stdlib. If you've got a binary tree that can support Trie (which I believe means a slower log N, but still log N, for the relevant operations?), why not inherit collections.abc.MutableTrie, collections.ABC.MutableSortedMapping?