Re: practical functional programming

[qrczak@knm.org.pl (Marcin 'Qrczak' Kowalczyk)]

Mon, 06 Nov 2000 10:15:30 -0800, Chris Hecker <checker@d6.com> pisze:

> 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?  How does
> this work out in practice?

It depends on how the symbol table is implemented.

With balanced binary trees element search costs log(N) and obtaining
an updated mapping costs log(N). Updating must copy the path from
the root to the place where the change is being made.

With hash tables search costs a constant time but obtaining an updated
mapping costs N.

There is a tricky idea providing fast arrays with a functional
interface. A mutable array is kept under a mutable reference.
Obtaining an updated array does the update in place and then replaces
the contents of the old reference by a data structure which refers
to the new copy and tells which element to replace by which old
value. So values from which other versions were derived behave as
before, even though their representation changes. Accessing older
versions becomes slower and slower as more updates are being made.

There is a complex imperative implementation here, especially as we
must deal with cases when the updated version is no longer used and
there is a chain of updates starting from an older copy. When versions
diverge too much, probably it's time to make separate copies. I'm
not sure how all details should be done. But once it is done, usage
of these arrays is completely functional.

> Is there some sort of reference counted sharing going on, or are
> there actually two copies of the data in memory if you wrote your
> example in caml?

Everything not explicitly copied is shared, but OCaml's implementation
of the garbage collector does not use reference counting.

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZASTĘPCZA
QRCZAK