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