Proposal: Partitionable goes somewhere + containers instances

[Milan Straka]

Hi all,

> -----Original message-----
> From: Ryan Newton <rrnewton at gmail.com>
> 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/5d6b07f69e8396023101039a4aaab619af41c810
> 
> (2) a splitTree function [1].  A patch can be found here:
> https://github.com/rrnewton/containers/commit/6153896f0c7e6cdf70656dc6b641ce61711175f8
> 
> 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