Indiana University Bloomington

School of Informatics and Computing

Technical Report TR330:
Graph Algorithms in a Lazy Functional Programming Language

Yugo Kashiwagi and David S. Wise
(Apr 1991), 12 pgs.
[Proc. 4th Intl. Symp. on Lucid & Intensional Programming, Menlo Park, CA: SRI Intl. (April 1991), 35-46.]
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: