🚀 go-pugleaf

In article <REDDY.91May28195125@reddy.cs.uiuc.edu> reddy@reddy.cs.uiuc.edu (Uday S. Reddy) writes:

   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.

I think this is the wrong approach. Using data structures based on
reverse diffs (as in RCS), an update involving side effects:

   val new_graph = (Graph.update_add_edge(graph,from,to); graph)

is no more efficient (except for possibly a small, constant time
overhead) than a more functional formulation:

   val new_graph = Graph.with_edge(graph,from,to)

Therefore, the following claim doesn't quite hold:

      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".

Since both "updates" and lookups can be carried out in constant time
even in a purely functional setting using data structures based on
reverse diffs, this is not true.

   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.

The main problem is that most purely functional languages do not
provide data structures based on reverse diffs as primitives. If you
don't have side-effects in your language and only have data structures
like "list", "tuple", and "vector" built in, you lose, of course. (But,
by analogy, if you don't have "vector" in you language, you don't
get constant time lookups, so the fault is not with the functional
programming paradigm, but with the absence of the right primitive
data type.)

However, in a language like SML, you can isolate the side effects to
a small, abstract module and program your graph algorithms happily,
side-effect free, and efficiently.

						Thomas.