Re: [Haskell-cafe] Memoization local to a function
Thanks for all the hints and code provided, nevertheless, it implied another questions: 1) Am I right that MemoCombinators can be hardly ever used with hugs? If not, which guidelines to be used for installation... 2) Is there any paper/tutorial/wiki that describes, which local definitions/expressions are discarded/not shared after/to the next computation, that means separated closure is built for them? Dusan Henning Thielemann wrote: On Wed, 25 Feb 2009, Luke Palmer wrote: On Wed, Feb 25, 2009 at 10:38 AM, Dusan Kolar ko...@fit.vutbr.cz wrote: I have a function a computation of which is quite expensive, it is recursively dependent on itself with respect to some other function values - we can roughly model its behaviour with fib function (returns n-th number of Fibonacci's sequence). Unfortunately, it is not fib, it is far more complicated. Nevertheless, for demonstration of my question/problem I will use fib, it's quite good. I suggest using data-memocombinators for this rather than rolling your own. It accomplishes the same thing, but makes the choice of memo structure independent of the code that uses it (and Memo.integral has asymptotically better performance than a list). Nice to know that there is a package for this purpose. See also http://haskell.org/haskellwiki/Memoization ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Memoization local to a function
Thanks for all the hints and code provided, nevertheless, it implied another questions: 1) Am I right that MemoCombinators can be hardly ever used with hugs? If not, which guidelines to be used for installation... 2) Is there any paper/tutorial/wiki that describes, which local definitions/expressions are discarded/not shared after/to the next computation, that means separated closure is built for them? Dusan Henning Thielemann wrote: On Wed, 25 Feb 2009, Luke Palmer wrote: On Wed, Feb 25, 2009 at 10:38 AM, Dusan Kolar ko...@fit.vutbr.cz wrote: I have a function a computation of which is quite expensive, it is recursively dependent on itself with respect to some other function values - we can roughly model its behaviour with fib function (returns n-th number of Fibonacci's sequence). Unfortunately, it is not fib, it is far more complicated. Nevertheless, for demonstration of my question/problem I will use fib, it's quite good. I suggest using data-memocombinators for this rather than rolling your own. It accomplishes the same thing, but makes the choice of memo structure independent of the code that uses it (and Memo.integral has asymptotically better performance than a list). Nice to know that there is a package for this purpose. See also http://haskell.org/haskellwiki/Memoization -- Dusan Kolartel: +420 54 114 1238 UIFS FIT VUT Brno fax: +420 54 114 1270 Bozetechova 2 e-mail: ko...@fit.vutbr.cz Brno 612 66 Czech Republic -- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Memoization local to a function
Dusan Kolar wrote: Nevertheless, local version does not work. Restructure your code like this: fibL m = let allfib = 0:1:[allfib!!n + allfib!!(n+1) | n - [0..]] in allfib !! m fibL = let allfib = 0:1:[allfib!!n + allfib!!(n+1) | n - [0..]] in \m - allfib !! m i.e. move the definition of the memo table outside the scope of the specific parameter you want to memoise over. Cheers, Ganesh === Please access the attached hyperlink for an important electronic communications disclaimer: http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html === ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Memoization local to a function
On Wed, Feb 25, 2009 at 10:38 AM, Dusan Kolar ko...@fit.vutbr.cz wrote: I have a function a computation of which is quite expensive, it is recursively dependent on itself with respect to some other function values - we can roughly model its behaviour with fib function (returns n-th number of Fibonacci's sequence). Unfortunately, it is not fib, it is far more complicated. Nevertheless, for demonstration of my question/problem I will use fib, it's quite good. I suggest using data-memocombinatorshttp://hackage.haskell.org/cgi-bin/hackage-scripts/package/data-memocombinatorsfor this rather than rolling your own. It accomplishes the same thing, but makes the choice of memo structure independent of the code that uses it (and Memo.integral has asymptotically better performance than a list). Luke I want to store results in a list (array, with its strong size limit that I do not know prior to computation, is not suitable) and then pick them up using (!!) operator. Well, if the list is global function/constant then it works quite well. Unfortunately, this is not, what I would like to have. Nevertheless, local version does not work. Could someone point me to some text that explains it? Memoization text on wiki does not seem to be helpful. Time/operation consumption is deduced from number of reductions reported by hugs and winhugs (tested both on Linux and Windows). Thank you for hints, Dusan P.S. Code I used for testing. module Testmemo ( fibW , fibL , fibM ) where fibW m = allfib !! m where allfib = 0:1:[allfib!!n + allfib!!(n+1) | n - [0..]] fibL m = let allfib = 0:1:[allfib!!n + allfib!!(n+1) | n - [0..]] in allfib !! m fibM n = myallfib !! n myallfib = 0:1:[myallfib!!n + myallfib!!(n+1) | n - [0..]] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Memoization local to a function
On Wed, 25 Feb 2009, Luke Palmer wrote: On Wed, Feb 25, 2009 at 10:38 AM, Dusan Kolar ko...@fit.vutbr.cz wrote: I have a function a computation of which is quite expensive, it is recursively dependent on itself with respect to some other function values - we can roughly model its behaviour with fib function (returns n-th number of Fibonacci's sequence). Unfortunately, it is not fib, it is far more complicated. Nevertheless, for demonstration of my question/problem I will use fib, it's quite good. I suggest using data-memocombinators for this rather than rolling your own. It accomplishes the same thing, but makes the choice of memo structure independent of the code that uses it (and Memo.integral has asymptotically better performance than a list). Nice to know that there is a package for this purpose. See also http://haskell.org/haskellwiki/Memoization___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
