Re: practical functional programming

[Stephan Houben <stephan@pcrm.win.tue.nl>]

On Mon, 06 Nov 2000, Chris Hecker wrote:
 
> I guess my next question then would be related to efficiency: isn't there a lot of copying going on if you've got to make a new instance of your symbol table just to add an element?  

Well, one of the advantages of having a purely functional data structure is
that you can freely share substructures. So there is very little copying.
Because the updated structure shares most of its memory with the original
structure, holding on to both isn't prohibitively expensive.

Again, this makes it simple to "roll back" to a previous version.

> Again, I'm not saying efficiency is the only metric for software, but it does concern me when I see a large datastructure copied.

No copying. Just pointer sharing.

>  Is there some sort of reference counted sharing going on, 

Reference counting is a (bad) substitute for real garbage collection, such as
O'Caml has. No need for refcounting, since we have GC.

> or are there actually two copies of the data in memory if you wrote your
> example in caml?  

No, this is not the case. Most of the data is shared.

> I guess my hope would be that in the case where you
> didn't reference the old datastructure ever again you would get performance
> close to the equivalent imperative datastructure.

It depends on the data structure, but some of Okasaki's data structures come
close to this ideal.

> In the case where you did
> reference both old and new you'd get performance similar to writing an
> "undo-able" imperative datastructure from scratch, 

Writing an undo-able imperative data-structure is no easy job.
Most people would probably go for a functional data structure then.

For example: the new ReiserFs in Linux (journalling filesystem) needs
for its journalling a similar commit/roll-back functionality. Therefore, it
is based on balanced trees, which are a somwehat functional data structure.
(I definitely do not want to suggest that ReiserFs is somehow a purely
functional file system, just that the basic idea is somewhat similar to some
functional data structures.)

> possibly with an
> optimization for not accessing the old datastructure until the new one had
> been undone (like in your example, and I would assume that's the common case
> for using persistence).

I am afraid that compilers aren't that smart yet.

I think the bottom line is this: imperative datastructures are often (somewhat)
faster, but purely functional datastructures are more general. This shows the
importance of Okasaki's work: sometimes it is possible to have your cake and
eat it, too.

So now it is up to you to decide whether you need a purely functional or an 
imperative data structure. There is no hard&fast rule here: it depends
completely on the application. But the nice thing of O'Caml is that it gives you
the choice. Which is also the bad thing: if we were writing Perl, we would
almost always use hashes and not have to think about these issues.

Good luck with your decision,

Stephan

--  ir. Stephan H.M.J. Houben tel.
+31-40-2474358 / +31-40-2743497 e-mail: stephanh@win.tue.nl