Functional languages & support for memoization

Question

Do any of the current crop of popular functional languages have good support for memoization & if I was to pick one on the strength of its memoisation which would you recommend & why?

Update: I'm looking to optimise a directed graph (where nodes could be functions or data). When a node in the graph is updated I would like the values of other nodes to be recalculated only if they depend the node that changed.

Update2: require free or open-source language/runtime.

Answer 1

For Haskell, Conal Elliott has posted a beautiful blog entry on functional memo tries. The work is extraordinarily clever and quite deep, and Conal later extended it to polymorphic functions. No matter what language you use, this stuff is highly recommended, because it uncovers the deep ideas underlying memoization in functional languages.

However, looking at your update, it's not clear that memoization is really what you want. Your expanded problem statement (propagating updates through a directed graph) is an almost textbook example of incremental computation, on which a great deal of work has been done by Bob Harper and Umut Acar. I believe they have a free library written in Standard ML. Look at Umut's page on self-adjusting computation.

Answer 2

On Haskell, see this for a start.

For Lisp, this was the first hit from Google that looked relevant.

For F# this might be a good place to start.

Now I'm done Googling for you. Is any of this good support ? You decide :-)

Oh, I'd recommend Mathematica, but I understand that a lot of people are put off by its price tag. Strictly speaking it's probably more of a term-rewriting system than a functional programming system, and it's not pure in any senses of the word. But it does do memoization.

EDIT: I forgot Erlang, which has a lot of traction at the moment -- I don't know how but I expect it can do memoization.

Answer 3

Yeah, you don't want memoization at all, you want precise dependency tracking. You could use the Haskell Functional Graph Library (fgl) to create ur directed graph, then use the successor function to know precisely which nodes to update: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/fgl

This paper will greatly aid ind understanding the docs: http://web.engr.oregonstate.edu/~erwig/fgl/

The successor function is named suc, in module Data.Graph.Inductive.Graph

Going in a different direction, one popular functional language that supports this is Excel. :)