[Haskell-cafe] Re: Optimization problem

[apfelmus at quantentunnel.de]

Ross Paterson wrote:

> 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
> [...]
> 	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)
> 
> [...]
> Applying a tupling transformation to insert+uninsert gives your version.
> 
> It's interesting that these composed transformations don't seem to cost
> too much.

That the composed transformations are indeed cheap is not necessarily
disturbing. Let's call Bertram's original insert version "insertdelete"
from now on. When analyzing the magic behind, you do

ross_analysis :: ((bp,map') -> (bp',map)) -> (bp->bp', (bp,map') -> map)
ross_analysis insertdelete = (insert, uninsert)

Of course a tupling transformation will reverse this

tupletiple :: (bp->bp', (bp,map') -> map) -> ((bp,map') -> (bp',map))
tupletiple (insert,uninsert) = insertdelete

But as @djinn will tell you, "ross_analysis cannot be realized" :) So
the original version possesses additional computational power, it can
reverse everything it's doing with bp on the map'. uninsert does not
have information about the single steps that have been done, it only
knows what should come out. From that, it would have to reconstruct
quickly what happened, if it wants to be fast.

Regards,
apfelmus