[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

SRFI-101 ported to Kawa

FYI: I checked into Kawa's subversion repository a port of the SRFI-101
(Purely Functional Random-Access Pairs and Lists) reference implementation:

Noteworthy is that this is implemented using a RAPair class
that extends Kawa's generic pair type, which means that most code
that expects a standard list will work on ra-lists as well.

I re-wrote the lower-level parts in Java because I considered
using these lists pervasively for immutable lists (as returned
by the reader).  However, I don't think ra-lists are a good
general representation for that, because cdr may do memory allocation.
Traversal code (like map) goes to some convolutions to avoid that,
but user code can't (and shouldn't) do that.

Instead, I've been experimenting with a variation where each
interior node is also a pair, and each pair has a direct cdr link.
This makes the cdr operation (and thus traversal in general)
fast and cheap, while still providing logarithmic list-ref
and list-tail.  Thus I think it makes for a better general
replacement for immutable lists (i.e. something read can return,
by default).  The biggest downside is we lose random-access
update.  (If you allow modifying the car but not the cdr you can
still have random-access but non-functional update.)
Another downside is 2 extra fields in each pair compared
to plains lists.  Finally, cons is worst-case logarithmic, but
I think that is ok since it is still amortized constant.
	--Per Bothner
per@xxxxxxxxxxx   http://per.bothner.com/