Re: Functional Programming in the Larger or Functional Oriented Software Engineering

On Sat, Mar 31, 2007 at 03:13:52PM -0500, Matthew D Swank wrote:
> Joe Marshall wrote:
> >On 3/29/07, Matthew Swank <[email protected]> wrote:
> >>>
> >>What if resources aren't cheap, or I have to manage my own memory.  Is
> >>avoiding mutation still practical?
> >
> >It can be.  There are some interesting tricks.
> >
> >The first is memoization.  Pure functions never change their output
> >when given the same input, so you can save the results of a
> >computation in a table and just look up the answer the next time.
> >Although the table itself requires memory, it can save resources
> >in the long run because it avoids redoing any allocation performed
> >in intermediate computations.
> >
> >The second trick is truly awesome.  You can memoize CONS
> >using a technique called `hash consing'.  You keep a hash
> >table of your cons cells and when the user calls CONS, you
> >check to see if you have an existing CONS cell with the right
> >contents and use it instead.  Of course this only works if you
> >*never* mutate hashed conses.  There is a surprising additional
> >benefit of doing this.  If you think about it a bit, you'll realize that
> >this technique causes all your CONS cells to be interned.
> >This means that you can use EQ to compare lists in O(1) time.
> >There is yet *another* interesting benefit.  Tree structures that
> >are built out of CONS cells turn into directed acyclic graphs
> >with maximal sharing automatically.  This results in a substantial
> >space savings.
> >

Err, did you just illustrate how not using mutation can be beneficial in 
resource-constrained environments by introducing memoization and hash 
tables, both of which involve mutation?!?!

Regards,

Bob

-- 
But I ask you, what can a mathematician do without a sponge?

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFGDstMfb9wcmD+WN4RApSpAKDY0NovFxUVZzlU7UPBQAW/Jx/vEQCfdoPH
nj55mhL+L+A+d2T9yc5E8s8=
=s689
-----END PGP SIGNATURE-----