|
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
|
Trees with parent "pointers"
