[Haskell-cafe] Un-memoization

[oleg at okmij.org]

Victor Miller wrote:
> I was writing a Haskell program which builds a large labeled binary tree
> and then does some processing of it, which is fold-like.  In the actual
> application that I have in mind the tree will be *huge*.  If the whole tree
> is kept in memory it would probably take up 100's of gigabytes.  Because of
> the pattern of processing the tree, it occurred to me that it might be
> better (cause much less paging) if some large subtrees could be replaced by
> thunks which can either recalculate the subtree as needed, or write out the
> subtree, get rid of the references to it (so it can be garbage collected)
> and then read back in (perhaps in pieces) as needed.  This could be fairly
> cleanly expressed monadically.  So does anyone know if someone has created
> something like this?

Yes. I had faced essentially the same problem. It is indeed tricky to
prevent memoization: GHC is very good at it. The following article
explains the solution:

	``Preventing memoization in (AI) search problems''
	http://okmij.org/ftp/Haskell/index.html#memo-off