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.