[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Memoization as alternative to mutation



On Thu, 12 Feb 2004, Michael St. Hippolyte wrote:

> Hi all,
>
> I'm curious as to what is the language community's general feeling towards
> memoization and caching as a substitute for mutation.  I'm less concerned with
> labels (i.e. whether or not memoization counts as "pure" FP) than with
> usefulness.  Has memoization proven to be a useful way to implement things like
> sorting algorithms, parsers, design patterns, etc?
>

Packrat parsing is an interesting application of memoization in parsing -
at an increased storage cost (linear in the size of the program), you get
a linear time cost and stronger parsing ability than CFGs.

http://www.pdos.lcs.mit.edu/~baford/packrat/thesis/

cheers,
mrak

-- 
i daren't use punctuation
when arguing with legalists
	-- demmy