[racket] Compound mutable list manipulation - 2 qs

From: Rüdiger Asche (rac at ruediger-asche.de)
Date: Mon Feb 13 06:33:24 EST 2012

Hi there,

My application makes heavy use of potentially very large lists and  
needs to access them as efficiently as possible which is why I wrote  
my own list manager. Basically the "root" of the list representation  
is a mutable pair whose mcar points to the head of an mlist and whose  
mcdr points to the tail of the same list. This allows for efficient  
insertion at the tail and removal from the head. Needless to say, the  
lists can contain arbitrary racket data which can also contain  
instances of those same in-place manipulatable lists. This works  
fairly decently so far.

My questions:

1. I understand that mutable pairs are considered somewhat on the dark  
side of Scheme and Racket, and I can see why, but in my application I  
can't afford to a) permanently recur down lists to find the tail and  
b) permanently rebuild lists (if for example only one small element  
changes in the sublist of a complex list, there is no justification  
for rebuilding the entire list from scratch) and let the garbage  
collector take up all the work of digesting the leftovers. If Racket  
has some "cleaner" way to manipulate large lists with a reasonable  
degree of efficiency, I'd be thankful for pointers. Also if there are  
adverse side effects to this design, I'd be interested in learning  
about them.

2. I am looking for an abstraction that makes the use of this  
mechanism explicit in the code (iow, by looking at the code, one  
should be able to determine where this mechanism is used and clearly  
distiguish it from usages of other data types). In C++, one would  
typically use classes, but I'm not sure whether Racket classes allow  
the same degree of control over the internal representation of the  
data in it. Other choices would be syntactic abstractions (which  
wouldn't prevent improper usage of functions defined on the data, but  
I think I could live with that) or structures. What is the most  
rackety way to go about that kind of thing?


Posted on the users mailing list.