Proposal: Partitionable goes somewhere + containers instances
fox at ucw.cz
Sun Sep 29 11:22:13 UTC 2013
> -----Original message-----
> From: Ryan Newton <rrnewton at gmail.com>
> Sent: 29 Sep 2013, 04:21
> *class Partitionable t where*
> * partition :: t -> Maybe (t,t)*
> 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.
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
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.
More information about the Libraries