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