[Haskell-cafe] Un-memoization

[Edward Kmett]

It depends on how you are building the tree.

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'.

I blogged about it here:

http://comonad.com/reader/2011/free-monads-for-less/
http://comonad.com/reader/2011/free-monads-for-less-2/

and used it here:

http://comonad.com/reader/2011/free-monads-for-less-3/

Janis Voightländer has a paper on the simpler version from the first post
above as well

http://www.iai.uni-bonn.de/~jv/mpc08.pdf

However, to page out or recalculate, you are probably looking at a more
complicated construction.

-Edward

On Wed, Mar 21, 2012 at 9:55 PM, Victor Miller <victorsmiller at gmail.com>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?
>
> Victor
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120323/1c3a1606/attachment.htm>