Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!mintaka!ai-lab!life!tmb From: tmb@ai.mit.edu (Thomas M. Breuel) Newsgroups: comp.lang.functional Subject: Re: functional programming formulation of graph algorithms Message-ID: Date: 29 May 91 21:46:02 GMT References: <5332@ztivax.UUCP> Sender: news@ai.mit.edu Organization: MIT Artificial Intelligence Lab Lines: 53 In-reply-to: reddy@reddy.cs.uiuc.edu's message of 29 May 91 01:51:25 GMT In article 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.