Jaguarpaw Blog - Avoiding space leaks when deleting data

by Tom Ellis on 29th March 2013

Avoiding space leaks when deleting data

Suppose I have a Map and I get rid of a key that refers to a large data structure.

removeLargePart :: Map k a -> Map k a
removeLargePart = delete keyReferencingLargeDataStructure

Then I proceed to do a long computation that eventually references the map.

longComputation . removeLargePart

The large data structure cannot be garbage collected until the map is inspected and the removal forced, leaking space. We want to ensure that longComputation cannot start to be evaluated before removeLargePart. That way we know that the Map will be evaluated, and data that was deleted from it will be available for garbage collection, before longComputation runs.

Here’s a way we can ensure this

delete' :: k -> Map k a -> (Map k a -> r) -> r
delete' k m continueWith = let m' = delete k m
                           in m' `seq` continueWith m'

removeLargePart' :: Map k a -> (Map k a -> r) -> r
removeLargePart' = delete' keyReferencingLargeDataStructure

and instead of longComputation . removeLargePart we can have

\m -> removeLargePart' m longComputation

In terms of the Cont r monad this is

(uncont .) $ (return . longComputation) <=< (cont . removeLargePart')

uncont :: Cont a a -> a
uncont = flip runCont id

which is perhaps more confusing for small examples, but will help when the code gets complex.

Amanda Clare has discovered this kind of technique (as, I’m sure, have many others).