🚀 go-pugleaf

In article <5332@ztivax.UUCP> corvara@ztivax.UUCP (Dr Gerd Venzl) writes:

   Some months ago somewhere in the literature I found a statement like

      "Functional programming is not well suited for algorithms of graph
       theory as these usually make frequent use of side effects."

I am curious where exactly you found that quote.  

In any case, the reason graph algorithms cannot be efficiently
implemented in functional languages is that they involve "shared
updates".  Depth-first search, for instance, involves updating tags at
vertices to keep track of which vertices have been visited.
"Modifying" a tag means making a new graph which is same as the old
one except that one of its tags is changed.

The simplest way to handle these in existing pure functional languages
is to (abstractly) represent a graph as a finite map

	Vertex -> List(Edge)

Such maps can be implemented, in turn, by balanced search trees of
some kind to allow for (nondestructive) updating.  Of course, if you
are using an "impure" functional language with assignments, you can
use them to get what you want.  But, you should be careful not to
create awful side effects.

Researchers are working on notations for expressing sequentiality
constraints so that compilers can update data structures in place.
See the proceedings of the upcoming FPCA, for example.

Uday Reddy
--
Uday Reddy
Department of Computer Science
University of Illinois
1304 West Springfield Avenue
Urbana, IL 61801.