This page is part of the web mail archives of SRFI 101 from before July 7th, 2015. The new archives for SRFI 101 contain all messages, not just those from before July 7th, 2015.
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.