[Haskell-cafe] Re: Optimization problem

apfelmus at quantentunnel.de apfelmus at quantentunnel.de
Fri Sep 15 05:00:31 EDT 2006

Ross Paterson wrote:
> 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.

No. The point is that in
   let blueprint = empty
       (_,m) = splitSeq' blueprint $ concat $ repeat [(1,'a'),(2,'b')],
the map m contains only as many keys as there are in blueprint, i.e. not
a single one! After munching the first (1,'a'), the first recursive call
to splitSeq', the returned map m' fulfills
   toList m' == [(1,"aaaaa...")]

The trick is to throw away all keys from the future, so that there is no
need to wait on them.

Also, if your argument would have been correct, then the version without
balancing wouldn't work either because insert already exchanges Leafs
for Nodes in m. So the top of the map would be unavailable until all
Leafs have been exchanged.


More information about the Haskell-Cafe mailing list