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

[Mario Blažević]

On 09/29/13 08:20, Edward Kmett wrote:
> I don't know that it belongs in the "standard" libraries, but there 
> could definitely be a package for something similar.
>
> ConstraintKinds are a pretty hefty extension to throw at it, and the 
> signature written there prevents it from being used on ByteString, 
> Text, etc.
>
> This can be implemented with much lighter weight types though!
> class Partitionable t where
>      partition  ::  Int  ->  t  ->  [t]

     I'm not sure why I don't already have this method in the 
FactorialMonoid class, but I'll happily add it if anybody wants it. 
Probably under the name splitEvery, since I already have splitAt.

     I'm not sure this is actually the best answer to Ryan's original 
plea, because I thought the idea was to let the original monoid "split 
itself" in an optimal way, which would preferably be an O(1) operation. 
Then again, this could be overly optimistic. For example, Map is defined as

data Map k a = Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a)
| Tip

so the simple O(1) split would produce three submaps, the middle one 
having only one element. This operation would not be very 
parallelization-friendly.

     That is not particularly surprising, since parallelization was not 
the main concern when Data.Map (or containers) was originally written. 
The main goal, as it should have been, was optimizing the containers for 
sequential execution speed. A containers-like package optimized for easy 
and efficient parallelization would have to be written almost from scratch.