[<<][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][>>][..]