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

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:
http://www.st.cs.uni-sb.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf
using lazy data structures, self-reference is easy, and can be
represented by lambda terms, which eventually boil down to the
Y-combinator.
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.
http://www.csse.monash.edu.au/~lloyd/tildeFP/1989SPE/
http://www.haskell.org/sitewiki/images/1/14/TMR-Issue6.pdf
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.

[Reply][About]

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