At 16:24 27/07/04 +0000, Tom Hofte wrote:
Hi,
I want to use the memo function for implementing a dynamic programming algorithm in Haskell. This is needed to cache intermediate results. Can anyone tell me where I can find some examples that use the memo function or even a tutorial.
As I understand it, this is not so much a "memo function" as a programming technique called "memoization". I've not seen this explained clearly in any single place, but my understanding is this: - rather than using a function to perform a calculation, use some kind of indexed data structure to hold the results, initialized with appropriate expressions - lazy evaluation means actual calculation of any value in the structure is suspended until it is actually needed, at which point the suspended calculation is replaced by the resulting value. - subsequent accesses to a previously calculated value simply return that value, hence the cache-effect. I'm expecting that others will correct me if I got that wrong, but I think that's about how memoization can be used. Googling for "Haskell memoization" returns a couple of examples (Fibonacci calculation is a popular one); I didn't see a clear tutorial there, but I didn't look beyond the first few hits. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact
Graham Klyne <GK@ninebynine.org> writes:
I want to use the memo function for implementing a dynamic programming algorithm in Haskell.
- rather than using a function to perform a calculation, use some kind of indexed data structure to hold the results, initialized with appropriate expressions - lazy evaluation means actual calculation of any value in the structure is suspended until it is actually needed, at which point the suspended calculation is replaced by the resulting value.
I'm not sure about the theoretically correct definition of dynamic programming, but I think you're onto it. Note that it doesn't have to be lazy, you can calculate the values for the complete space if you want. Very useful for any kind of recursive function that calls itself more than once, but with decreasing argument values. Typical for graph or graph-like algorithms (HMM probabilities, sequence alignment). -kzm -- If I haven't seen further, it is by standing in the footprints of giants
Tom Hofte wrote:
I want to use the memo function for implementing a dynamic programming algorithm in Haskell. This is needed to cache intermediate results. Can anyone tell me where I can find some examples that use the memo function or even a tutorial.
Hi Tom, I like Byron Cook's paper about disposable memo functions: <http://www.cse.ogi.edu/~byron/memo/dispose.ps> -- Daan.
Thanks,
Tom Hofte
------------------------------------------------------------------------ MSN Search, for accurate results! click here <http://g.msn.com/8HMAENNL/2734??PS=47575>
------------------------------------------------------------------------
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Hi Tom,
I want to use the memo function for implementing a dynamic programming algorithm in Haskell. This is needed to cache intermediate results. Can anyone tell me where I can find some examples that use the memo function or even a tutorial.
Here are some refs Hughes, 1985. @inproceedings{hughes:lazy-memo, TITLE = {{Lazy Memo-functions}}, AUTHOR = {R. J. M. Hughes}, BOOKTITLE = {{Proceedings 1985 Conference on Functional Programming Languages and Computer Architecture}}, ADDRESS = {Nancy, France}, YEAR = {1985} } (I think this appeared in LNCS) or Ralf Hinze. Memo functions, polytypically!. In Johan Jeuring, editor, Proceedings of the Second Workshop on Generic Programming, WGP 2000, Ponte de Lima, Portugal, 6th July 2000, see http://www.cs.uu.nl/~johanj/wgp2000/wgp2000cfp.html#Programme Cheers, Johan
Tom writes:
I want to use the memo function for implementing a dynamic programming algorithm in Haskell. This is needed to cache intermediate results. Can anyone tell me where I can find some examples that use the memo function or even a tutorial.
You should also look at Stretching the storage manager: weak pointers and stable names in Haskell Simon Peyton Jones, Simon Marlow, Conal Elliott IFL'99 http://research.microsoft.com/Users/simonpj/Papers/weak.htm which gives an example of a general memoising function "memo", which uses weak pointers to manage storage sensibly. --KW 8-) -- Keith Wansbrough <kw217@cl.cam.ac.uk> http://www.cl.cam.ac.uk/users/kw217/ University of Cambridge Computer Laboratory.
participants (6)
-
Daan Leijen -
Graham Klyne -
Johan Jeuring -
Keith Wansbrough -
Ketil Malde -
Tom Hofte