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