Lambda the Ultimate

inactiveTopic Trees with parent "pointers"
started 2/20/2003; 12:55:08 AM - last post 2/20/2003; 12:55:08 AM
Ehud Lamm - Trees with parent "pointers"  blueArrow
2/20/2003; 12:55:08 AM (reads: 2059, responses: 0)
Trees with parent "pointers"
The subject of creating cyclical data structures in a functional language has been discussed on LtU before. Now Oleg shows that we can create DAGs and general cyclic data structures even in a strict language!

The paradoxical tree is built by a procedure add-thunk-parent-pt, which is defined in section 'Solution 3' of the source code. The procedure is deceptively simple. It took 21 lines of Scheme code to implement the algorithm and 26 (full-length) lines of comments to explain it (see the section about thunked parent pointers).

The backlink isn't really a reference, it is a nullary procedure, a thunk, which, when applied, yields the node that is the parent of the current node.

Posted to functional by Ehud Lamm on 2/20/03; 12:58:14 AM