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

Re: functional languages ill-suited for large programs?



   Cc: Vadim Nasardinov <el-vadimo@comcast.net>, ll1-discuss@ai.mit.edu
   From: Jim Blandy <jimb@redhat.com>
   Date: 31 Oct 2003 17:14:57 -0500
   ...
   That is, whether or not it's *worthwhile* to memoize a function, a
   pure lazy language doesn't even allow me to *express* a memoized
   function behind a purely functional interface, even though the
   resulting behavior is purely functional.

In Haskell, this:

  fib 0 = 0
  fib 1 = 1
  fib n = fib (n - 1) + fib (n - 2)

is a very inefficient way to compute factorial, whereas this:

  fib = ((map fib' [0 ..]) !!)
    where
      fib' 0 = 0
      fib' 1 = 1
      fib' n = fib (n - 1) + fib (n - 2)

is a memoized version that executes quite quickly.  It seems to me that I
have just expressed the notion of a memoized function in a purely
functional language.