Re: Proposal: Partitionable goes somewhere + containers instances

Hi all,

-----Original message----- From: Ryan Newton Sent: 7 Oct 2013, 00:16

Ok, so we've narrowed the focus quite a bit to JUST exposing enough from containers to enable a third-party library to do all the parallel traversals it wants. Which of the following limited proposal would people like more?

(1) Expose Bin/Tip from, say, Data.Map.Internal, as in this patch:

https://github.com/rrnewton/containers/commit/5d6b07f69e8396023101039a4aaab6...

(2) a splitTree function [1]. A patch can be found here: https://github.com/rrnewton/containers/commit/6153896f0c7e6cdf70656dc6b641ce...

The argument for (1) would be that it doesn't pollute any namespaces people actually use at all, and Tip & Bin would seem to be pretty darn stable at this point. The only consumers of this information in practice would be downstream companion libraries (like, say, a parallel traversals library for monad-par & LVish!) Those could be updated if there were ever a seismic shift in the containers implementations.

I am strongly against (1). Exposing internal representation seem really wrong. FYI, I am planning to change the representation of Data.Map and Data.Set to a three constructor representation (I have already some benchmarks, halving time complexity of fold and decreasing memory usage by ~ 20%). So no, the internal representation is subject to change and I do not want it to become part of API. As for (2), I am not very happy about the type -- returning _three_ maps makes some assumptions about the internal representation. This can be seen when considering IntMap.splitTree -- there are no three IntMaps to return in a IntMap.splitTree, only two. What about the list version splitTree :: Map k a -> [Map k a] If splitTree is INLINE, I think we can assume the deforestation will happen. That would allow us to define splitTree for IntMap too. If someone is worried, could they check that deforestation does really happen? Cheers, Milan