Sat Apr 19 10:28:53 EDT 2008

graphs and FP

i never quite understood how to deal with graphs in FP. in EOPL
there's a point where circular reference is avoided by delaying
linkage. i think at the point where environments are implemented. at
the time it struck me as odd..

so, what is a graph? it's a map::  node -> (listof node)

whether children are ordered or not, listof can be setof

the problem with graphs is that nodes refer to one another. let's
first try to represent a graph as a tree.

see also zipper:

using lazy data structures, self-reference is easy, and can be
represented by lambda terms, which eventually boil down to the

EDIT: the idea seems to be to represent the graph as a lazy structure
that can generate a 'local tree expansion' or something.. a bit like
manifolds and R^n patches.

EDIT: what i'm looking for is called circular programming.

basicly: you need lazy evaluation to build graph structures: a pointer
to a structure can be available while the structure itself is as of
yet unevaluated, and as such can reference itself.