Tom Hawkins wrote: > After programming in Haskell for about a year now, I have found it > allows we to quickly develop initial programs; thanks to the > expressiveness of the language and type system. But due to > performance concerns, I typically have to restructure the initial > program, guided by profiling, to reduce time or memory consumption. > Many times, this refactoring process helps illuminate a better > strategic approach to the program. But very often, only a few > inefficient functions need to be equipped with memoization. > > I can certainly speed up these functions with explicit memoization, > usually by threading a Map or Set through the recursive decent. But > doing so always degrades the legibility of the original function. Are > there any tools to automate this process, so as not to clutter the > code with "Have-I-been-here-before?" tests and supporting data > structures? To what extent do Haskell compilers use memoization? Is > there any way to guide automatic memoization? > > Also, do any compilers use profiling data to enable or re-adjust > memoization caches of the worst offenders? In ECAD, we would call > this an in-place optimization (IPO).
Memoization and lazy evaluation go hand in hand. Unless you need to do different things depending on the answer of the question "Have-I-been-here-before?" (most prominent example: depth first search), it is unlikely that you need to carry around a Data.Map at all. It can be filled "statically" by a circular program. Anyway, the ultimate way to exploit sharing of sub-computations and pruning search tree is to use equational reasoning. IMHO, the following talk and paper make a good introduction: Richard Bird. How to Write a Functional Pearl. ICFP 2006 http://icfp06.cs.uchicago.edu/bird-talk.pdf Graham Hutton. The countdown problem. Journal of Functional Programming, 12(6):609-616, November 2002 http://www.cs.nott.ac.uk/~gmh/countdown.pdf Regards, apfelmus _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
