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. Regards, apfelmus