[plt-scheme] mutable lists/dicts?

On Sat, Apr 10, 2010 at 2:08 PM, Eric Tanter <etanter at dcc.uchile.cl> wrote:
> Thanks for the answers.
>
> I know I can get what I want with vectors or hash tables, but I'm still trying to figure out the design decisions for mutable lists. If someone is used to association lists, then it seems natural (by extension) to use mutable association lists.
>
> On Apr 10, 2010, at 10:05 AM, Matthew Flatt wrote:
>> At Sat, 10 Apr 2010 09:47:09 -0400, Carl Eastlund wrote:
>>> I'm not sure why mutable lists aren't dictionaries, though.
>>
>> Mutable association lists don't really fit the dictionary API:
>> If you want to extend an empty mutable association list, then you need
>> `dict-set!' to return a mutable pair, rather than void. Also, the empty
>> mutable association list has the same representation as an association
>> list.
>
> Yes, that's indeed quite odd.
> Why not having a separate representation (eg '{}) with the semantics being that you get a fresh empty mutable list?

Scheme's mutable lists aren't like, for instance, the Java List
interface.  It's not a single container to which you can mutably add
and remove elements.

A Scheme mutable list is a linked list whose cons-cells have mutable
car and cdr fields.  The empty mutable list is the same value as the
empty immutable list: null.  Null is not a mutable value; if you want
to add elements, you have to create a new cons cell.  Similarly, if
you have (mcons 1 null), you have a 1-element mutable list, but no
amount of mutation will remove that one element.  You can change the
first element to 1 or 2, you can change the tail to some other list,
but you can't mutate an mcons into an empty list.

This representation has been around as long as Scheme has; the
presence of immutable lists is actually new, and the scheme/dict
representation is even newer (and not a part of the standard at all --
it is purely a PLT invention).  So mutable lists were not designed
with a mutable dictionary interface in mind (or at least not this
one).

--Carl