On Fri, 20 Aug 2004, Richard Jones wrote:
> I think this has been discussed before, but I'd like to see a
> structure which lets you build a normal list, element at a time, and
> then "freeze" it to create a real list.
> Normally to do this one has to build the list backwards and then call
> List.rev as the final step. This is unnecessarily inefficient.
> _However_, if one abuses Obj.magic, then it should be possible to keep
> a pointer to the last element of the list as one is building it up,
> then mutate the (normally immutable) last element to append to the
> list. This would obviously have to be hidden behind an abstract type
> for safety. Finally the "freeze" operation would return the actual
> list and cause the abstract type to be forgotten.
If I understand you correctly, you're basically talking about taking the
trick we use in the ExtLib List module and exporting it so that anyone can
use it. I think this is a bad idea.
The core reason I think it's a bad idea is that immutability is often an
advantage. Being able to share the tails of lists can often create
efficiencies that mutable lists can't provide. An example of this: I was
playing with some code recently that was doing a breadth-first graph
traversal, and I wanted to keep track of my path through the graph. So I
simply kept a list of what nodes I had visited in a list. Whenever I
followed an edge of the graph, I prepended the new node onto the list. I
ended up with a large set of lists, most of which shared tailed.
The ExtLib List module mutates lists, but it's careful to only mutate
lists it knows no one else can see. The solution isn't to make lists
semi-mutable, it's to think differently. Instead of looking for the
solution with the mutating list, look for the solution with the immutable
Note that having a different data structure which is a mutable doubly
linked list is a completely different case.
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
- Gene Spafford