Re: Proposal: Partitionable goes somewhere + containers instances

Hi Ryan,

-----Original message----- From: Ryan Newton 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