Mon Sep 17 16:06:58 CEST 2007
linear structures, variables and cycles
in a linear structure (tree or acyclic graph if hash consing is used)
cycles are not possible. so how do you represent datastructures that
have some form of self-reference?
the thing we're looking for here is something akin to the Y
combinator: instead of having a function refer to itself, a different
function is used to turn a function to "tie the knot".
let's start with:
i'll try to put it in my own words, see next post. the link above has
an interesting comment on self-application. also, the wikipedia page
has some interesting links:
so how to you apply this trick to data structures? my guess would be
to start from data structures in the lambda calculus, and then making
things more concrete.