[Prev][Next][Index][Thread]
Re: Question about collections
Bruce Hoult <brucehoult@pobox.com> wrote:
> In article <slrn8bbq2c.co0.neelk@brick.cswv.com>, neelk@alum.mit.edu wrote:
>
> > [*] O(1) head and tail methods, and O(log N) access and update of
> > arbitrary elements.
>
> Sounds cool.
It is cool. It's also fairly useless. :)
The O() hides some middling big constant factors. So unless you really
badly need both the list-like and array-like behavior, there are
better data structures to choose from. (There are even some O(1)
functional arrays, though the implementation is kind of tricky.)
But it's definitely a fun exercise.
> Is access to arbitrary elements by index or by key (i.e. are the keys
> arbitrary or are they sequential integers)?
By index, though naturally you could build a hash-table-like data
structure on top of it. (Though it probably makes more sense to use
something like an AVL or red-black tree rather than going to all that
trouble.)
> > Update is functional, in the sense that it creates
> > a new RAL rather than mutating the old one.
>
> Presumably, that means that update actually creates O(log n) nodes of a
> tree-structure (from the head down to the element that changed), rather
> than a whole new RAL?
Yep.
> I'm not sure that it fits in the the existing Dylan collection classes, at
> least if you plan to use element-setter() and remove-element!()) to
> implement updating.
Element-setter needs to return the value of the right hand side (so
you can do things like "x := y := 42;"), so update for a random
access list can't be a method of element-setter. So I created an
explicit update(ral, index, value) => (new-ral) method. It's not
beautiful, but it's clear.
Neel
References: