[plt-scheme] self-referential data structures

Stephen Bloch wrote:
> BTW, I just wrote up a Java version of this approach, with methods
> atRightEnd(), atLeftEnd(), getLeft, getRight, insertLeft, insertRight, 
> moveLeft, moveRight, removeLeft, and removeRight.  It's all purely 
> functional, and it all seems to work.  And, of course, it takes about 
> five times as much code as it would take to do the same thing in Scheme :-)

This structure and the operations you describe are usually called a 
zipper [1]. You can build one for any algebraic data type - that is, 
trees of every kind as well as lists.

Huet's justification for publishing a paper on it is that it's something 
  obvious enough to get occasionally reinvented, but not obvious enough 
to become folklore. Oh, and it's dead useful. :)

Neil


[1] Gérard Huet. Functional Pearl: The Zipper. JFP 1997.