[Haskell] Re: Profiling Feedback to Optimize Memoization Caching

apfelmus at quantentunnel.de apfelmus at quantentunnel.de
Fri Feb 23 15:31:41 EST 2007

apfelmus at quantentunnel.de wrote:
> 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

Concerning memoization and sharing, I think I should add

   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

   Richard Bird and Ralf Hinze. Functional pearl: Trouble shared
   is trouble halved.
   In Johan Jeuring, editor, Proceedings of the ACM SIGPLAN 2003
   Haskell Workshop, Uppsala, Sweden, August 28, 2003, pp 1-6

Of course, there is also the classic book

   Richard Bird and Oege de Moor. Algebra of Programming.
   Prentice Hall, 1996.

but it's not introductory in nature. It seems to be out of print, is
there any way to get a (perhaps electronic) copy?


More information about the Haskell mailing list