It depends on how you are building the tree.<div><br></div><div>If you are building up the tree from repeated substitution at the leaves and never reference its body before you do the final fold, you may be able to exploit the fact that trees form a free monad, and that there is a nice construction for increasing the efficiency of substitution into free monads that has the side-effect of making them 'memoryless'.</div>
<div><br></div><div>I blogged about it here:</div><div><br></div><div><a href="http://comonad.com/reader/2011/free-monads-for-less/">http://comonad.com/reader/2011/free-monads-for-less/</a></div><div><a href="http://comonad.com/reader/2011/free-monads-for-less-2/">http://comonad.com/reader/2011/free-monads-for-less-2/</a></div>
<div><br></div><div>and used it here:</div><div><br></div><div><a href="http://comonad.com/reader/2011/free-monads-for-less-3/">http://comonad.com/reader/2011/free-monads-for-less-3/</a></div><div><br></div><div>Janis Voightländer has a paper on the simpler version from the first post above as well</div>
<div><br></div><div><a href="http://www.iai.uni-bonn.de/~jv/mpc08.pdf">http://www.iai.uni-bonn.de/~jv/mpc08.pdf</a></div><div><br></div><div>However, to page out or recalculate, you are probably looking at a more complicated construction.</div>
<div><br></div><div>-Edward</div><div><br></div><div><div class="gmail_quote">On Wed, Mar 21, 2012 at 9:55 PM, Victor Miller <span dir="ltr"><<a href="mailto:victorsmiller@gmail.com">victorsmiller@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">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?<br>
<font color="#888888">
<br>Victor<br>
</font><br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div>