[Haskell-cafe] Optimization problem

[Ross Paterson]

On Thu, Sep 14, 2006 at 05:22:05PM +0200, Bertram Felgenhauer wrote:
> [much subtle code]
> We can now build the splitStream function, using the following helper
> function:
> 
> > splitSeq' :: Ord a => Map a () -> [(a,b)] -> ([(a,[b])], Map a [b])

This works for infinite lists if there is no balancing, but if insert does
balancing, the top of the map will not be available until the last key
is seen, so splitSeq' could only be used for finite chunks.  Then you'll
need a way to put the partial answers together.  It might be possible
to amortize the cost of that for an appropriate choice of chunk length.
It would also cost some laziness: the chunked version would work for
infinite lists, but wouldn't produce all the output for a partial list.