[Haskell-cafe] Optimization problem

[Ross Paterson]

On Fri, Sep 15, 2006 at 05:13:29AM +0200, Bertram Felgenhauer wrote:
> Just to prove the point, here's the same code with balancing:

How embarrassing.  Still, your code is quite subtle.  As penance, here's
my explanation, separating the main idea from the knot-tying.

The ingredients are a map type with an insertion function

	data Key k a = ...
	instance Functor (Map k)

	insert :: Ord k => k -> a -> Map k a -> Map k a

with a partial inverse

	uninsert :: Ord k => k -> Map k () -> Map k a -> (a, Map k a)

satisfying

	uninsert k (fmap (const ()) m) (insert k v m) = (v, m)

for any map m not containing k.  We also need an update function

	update :: Ord k => k -> (a -> a) -> Map k x -> Map k a -> Map k a

where the two map arguments have the same shape.  Then splitSeq becomes:

	splitSeq :: Ord a => [(a,b)] -> [(a,[b])]
	splitSeq = fst . splitSeq' Leaf

	splitSeq' :: Ord a => Map a () -> [(a,b)] -> ([(a,[b])], Map a [b])
	splitSeq' bp [] = ([], map (const []) bp)
	splitSeq' bp ((a,b):xs)
	  | member a bp =
		let (l, m) = splitSeq' bp xs
		in  (l, update a (b:) bp m)
	  | otherwise =
		let bp' = insert a () bp
		    (l, m') = splitSeq' bp' xs
		    (bs, m) = uninsert a bp m'
		in ((a, b : bs) : l, m)

Applying a tupling transformation to insert+uninsert gives your version.

It's interesting that these composed transformations don't seem to cost
too much.