Proposal: Partitionable goes somewhere + containers instances

[Milan Straka]

Hi Ryan,

> -----Original message-----
> From: Ryan Newton <rrnewton at gmail.com>
> Sent: 7 Oct 2013, 13:41
>
> Hi all,
> 
> Thanks for more feedback.
> 
> I tend to not be afraid of the ".Internal" module that exposes stuff that
> changes, with appropriate caveats.  But it also seems like relatively
> little effort to have a cleaner public "splitTree" interface in this case,
> hopefully without extra overhead.
> 
> I propose to test simple use cases of a tuple and list version of splitTree
> and check out the deforestation properties.
> 
> Milan, I know the three-tuple version looks weird.  But since it's OK for
> some of those three chunks to be empty I think most future implementations
> would have an easy way to maintain compatibility, wouldn't they?

Yes, they would. Nevertheless, it seems to me that because a Map can be
splitted in one, two or three subtrees, it would make sense for
splitTree to return either zero, one, two or three subtrees, instead of
three, some of them empty.

> UNLESS, that is,y our new changes involve trees that would expose
> *more*than three-way-splits at a time (4-way, 5-way, etc).  Do they?

No, they do not. A limit of three subtrees is fine for containers
(3 for Set/Map, 2 for IntSet/IntMap in all planned improvements).

But consider for example unordered-containers. The HashMap is a multiway
tree with branching factor 1-16.

On that account, maybe we should use a different name than splitTree --
I do not like the Tree in the name, because tree is only a particular
data structure (for example, IntSet is actually a dense compressed trie).
What about something in the lines of 'divide'?


Only to be sure -- I support the list version provided that its
performance is not worse than the tuple version. I did some tests with
lists only (not Map) and it seems it is fine. But a thorough test is
still needed.

Cheers,
Milan