Graph Algorithms in a Lazy Functional Programming Language

(Apr 1991), 12 pgs.

[Proc. 4th Intl. Symp. on Lucid & Intensional Programming, Menlo Park, CA: SRI Intl. (April 1991), 35-46.]

**Abstract:**-
Solutions to graph problems can be formulated as the fixed point of a set of recursive equations. Traditional algorithms solve these problems by using pointers to build a graph and by iterating side effects to arrive at the fixed point, but this strategy causes serious problems of synchronization under a parallel implementation. In denying side effects, functional programming avoids them, but it also precludes known algorithms that are uniprocessor-optimal.
Functional programming provides another, translation scheme that computes the fixed point without relying on the operational concept of a ``store''. In this approach, laziness plays an essential role to build a cyclic data structure, a graph, and to implement iteration as streams. The resulting algorithm is not optimal on uniprocessors but, avoiding side effects, the algorithm suggests a promising, more general approach to multiprocessor solutions.

**Available as:**

- Compressed PostScript (51 KBytes)
- PostScript (via FTP download)
- PDF (140 KBytes)