[racket] Compound mutable list manipulation - 2 qs

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi Rüdiger,

On 13-02-12 12:33, Rüdiger Asche wrote:
> 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.

To get the best suggestions on alternative data structures you should
say a little more about wha your program does and thus needs. However
if all you're interested in is adding to the back and removing from
the front, that is a queue, you can implement one using two lists
without mutating the lists. One list represents the front and you can
cdr down it efficiently, the other list represents the back in reverse
and you cons elements onto it to add elements to the back of the
queue. Whenever the front list becomes empty you reverse the back list
to form the new front and the back becomes empty. This way you get a
queue with O(1) amortized enqueue and dequeue operations.

> 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?

You can hide the internals of your data strucutre in a module and only
expose (provide) those functions/things that are part of the public
interface.

Marijn

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.18 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk85EksACgkQp/VmCx0OL2xsmgCfeSpZ7rPoCIJqv4Mqqgnd+GCI
9MEAnj3T7pcTjGUBNq75v2iwr9mLo/SJ
=Yj5D
-----END PGP SIGNATURE-----