Re: [Haskell-cafe] Proposal: Partitionable goes somewhere + containers instances

Hi Ryan,

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