firstname.lastname@example.org (Andrew Koenig) writes:
> Here is a somewhat simplistic example. The following ML code defines a
> binary-tree data structure where each node contains a value and is
> either a leaf or has two subtrees:
> datatype 'a Tree = LEAF of 'a | TREE of 'a Tree * 'a Tree
> But now suppose we want to be able to identify a specific subtree of a tree.
> If I had gone to the trouble of creating a tree abstraction in C++, I could
> identify a particular subtree by the address of its root. But there's no
> corresponding facility in ML. Trees are values, and although one can compare
> them for equality, there is no notion of object identity.
Absolutely correct and correctly so.
If two things LOOK the same, then they ARE the same. It's called
"referential transparency" and it's a Good Thing, as opposed to
"pointers" which are a Bad Thing. Why confuse your life with "object
And why do you want to use the memory address for object identity to
identify it --- an address can change during garbage collection. Why
not use a time stamp of object creation? Oh, it's for efficiency
reasons, you say ... ah-ha!
But let's suppose that you really really really do need to identify a
particular subtree. In other words, you want to NAME it. No problem:
just create a dictionary (hash table) that maps names to subtrees.
That'll let you have two differently named entries which might happen
to have the same values. And it won't expose pointers. And it'll be
Or, perhaps you need names attached to the nodes; then define:
datatype 'a NamedTree = LEAF of 'a
| TREE of string * 'a NamedTree * 'a NamedTree
It's trivial to translate between NamedTree and Tree and you can also
combine NamedTree with a dictionary to allow fast access to individual
Repeat after me: "if two things look the same and act the same, then
they are the same". Don't depend on some hidden property (pointer) to
differentiate them. If there are important differences, then don't be
shy: bring them out in the open and NAME them.
[I once took an object-oriented database that used object-IDs and
translated it to a relational form which just used names for things;
performace improved by about about an order of magnitude. But that's
another rant for another day ...]
Peter Ludemann +1.415.813.6806 (fax: +1.415.813.7499)
Software Architect email@example.com
InXight Software, Inc. http://www.inxight.com
PAHV 105, 3400 Hillview Ave., Palo Alto, CA 94304