[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Date: Thu, 17 Sep 2009 22:32:47 -0400
From: David Van Horn <dvanhorn@xxxxxxxxxxxxxxx>
There are benchmarks in the Okasaki paper. To me, the important cases
are lookup and update. These things are simply not feasible using
sequential lists. What this means is that algorithms where you might
otherwise use a vector and mutation, you can now use a list and remain
functional (and thus thread-safe, etc).
Of course. But if these programs would otherwise use vectors, is
constant-time CONS important to them? For example, would they be just
as well served by bounded-balance binary trees, or what Stephen Adams
calls weight-balanced binary trees? I have sometimes pondered the
merit of a Lisp system with those as the basic data structure, rather
than lists, which would admit sequences, sets, and associations whose
common operations all run in logarithmic or linearithmic time.