[<<][staapl][>>][..]

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:

http://scienceblogs.com/goodmath/2006/08/why_oh_why_y.php

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:

http://en.wikipedia.org/wiki/Y_combinator

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.

[Reply][About]

[<<][staapl][>>][..]