Proposal: Partitionable goes somewhere + containers instances

[Milan Straka]

Hi Ryan,

> -----Original message-----
> From: Ryan Newton <rrnewton at gmail.com>
> Sent: 29 Sep 2013, 04:21
>
> <snip>
>
> *class Partitionable t where*
> *  partition :: t -> Maybe (t,t)*
>
> <snip>
> 
> So what I really want is for the *containers package to please get some
> kind of Partitionable instances! * Johan & others, I would be happy to
> provide a patch if the class can be agreed on. This is important because
> currently the balanced tree structure of Data.Set/Map is an *amazing and
> beneficial property* that is *not* exposed at all through the API.

Some comments:

1) containers are a boot package (http://ghc.haskell.org/trac/ghc/wiki/Commentary/Libraries)
   therefore its dependencies have to be boot packages too. If
   Partitionable gets into base or some other boot package, fine :)

2) IntMap/IntSet have different partitioning operation than Map/Set:
     partition :: IntMap a -> Either IntMap (IntMap a, IntMap)
      partition :: Map k v -> Either Map (Map, k, v, Map)
   Nevertheless, IntMap/IntSet are not well balanced, so maybe it would
   be fine to have partition working for Map/Set.

3) Partition somehow exposes internal structure, which forces us to only
   some implementations. Nevertheless, I doubt the representation of
   containers will change wildly (although I am planning to add data
   constructor to Map/Set shortly, so you never know).

It seems that the best course of action would be to ignore the
Partitionable class and instead provide methods in the containers to
allow splitting.

The question is how should the API look like. Currently IntMap and
IntSet are deliberately as close to Map and Set as possible. Introducing
this splitting operation would enlarge the difference between them.
But as noted, we could provide split only for Map and Set, as
IntMap/IntSet are not well balanced anyway.

Cheers,
Milan