# hash & balanced trees

Erik Ostrom (eostrom@research.att.com)
Tue, 01 Jul 1997 10:56:09 -0400

- Messages sorted by:[ date ][ thread ][ subject ][ author ]

    > > That's fine for mutable data type... but unless I'm mistaken MOO lists
    > > are not.
    > Not sure that one would want to replace the moo list data type with a hash
    > or tree.  Rather, by adding new builtin support for alternative types, it
    > gives programmers a choice.

    Yes.  However, I personally wouldn't add another aggregate data type that
    is mutable.  (There's one exception:  I might add a data type that's almost
    exactly like OBJ, but is garbage-collected.)  Mutable data in an environment
    that is expected to contain many programmers with... conflicting goals can
    be a pain.

    Does anyone know if there's a standard lecture on this yet?

    > Why not add both a $hash and a $tree =8?

    Well, the usual thing in MOO is to add data types that are defined only
    by their operations at the level of user code.  For example, lists are
    defined by their constructor syntax, dereferencing, range set, and a good
    number of other things.  Your average programmer doesn't have to know
    whether they're implemented as an array, a linked list, or some other
    data structure.

    So, in that tradition, my tendency would be to add a "dictionary" data
    type, which is defined by the ability to put stuff in and look stuff up
    by arbitrary keys.  Maybe there are hash tables in the server, maybe
    there are trees.  But it's an abstract data type as far as the MOO
    programmer is concerned.

    (Credit for this rant is due to Jay, who has finally got it through my
    thick head.)

    Of course, my meta-plan is to make it easier for OTHER programmers to
    add new data types, so you can experiment as much as you like with
    hash tables, binary trees, tries, splay trees, and so on.

    --Erik