apfelmus@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 http://www.informatik.uni-bonn.de/~ralf/publications/WGP00b.ps.gz 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 http://www.informatik.uni-bonn.de/~ralf/publications/HW2003.pdf 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? Regards, apfelmus