Re: functional languages ill-suited for large programs?

[Jim Blandy <address@hidden>]

Alan Bawden <Alan@LCS.MIT.EDU> writes:

>    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.

Yes, you have.  Please check my memory of Haskell: this computes
(lazily) an infinite list whose n'th element is fib' n, and then
curries the subscripting operator !! --- is that right?

But what if I needed to be able to forget old memoized values?
They're large objects, say, and the program's going to run for a very
long time passing the function an unbounded number of different
arguments.  The problem I'm getting at is, lazy evaluators can thaw
thunks, but can't "re-freeze" them (i.e., replace thawed values with
closures that can re-compute them on demand), the way deleting an
arg/result pair from the cache in a stateful language effectively
does.  If you needed to do that, it seems to me you'd have to
introduce some sort of state.

So while yours is a graceful example (and one that comes up in many
tutorials on Haskell, so I wish I had thought of it myself), I don't
think it addresses the original point: that concealed state is often
useful, but pure languages can't provide it without introducing
something monadish into the signature.

If you've got an argument that concealed state *isn't* often useful,
then that'd be a direct rebuttal.  Do people writing Haskell libraries
often find themselves introducing stateful character into interfaces
where the job at hand doesn't seem stateful?  If not, then the case I
brought up may not be too significant.