Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!zaphod.mps.ohio-state.edu!caen!news.cs.indiana.edu!ux1.cso.uiuc.edu!m.cs.uiuc.edu!m!reddy From: reddy@reddy.cs.uiuc.edu (Uday S. Reddy) Newsgroups: comp.lang.functional Subject: Re: functional programming formulation of graph algorithms Message-ID: Date: 29 May 91 01:51:25 GMT References: <5332@ztivax.UUCP> Sender: news@m.cs.uiuc.edu (News Database (admin-Mike Schwager)) Organization: /home/reddy/reddy/.organization Lines: 38 In-Reply-To: corvara@ztivax.UUCP's message of 27 May 91 13: 02:26 GMT Nntp-Posting-Host: reddy.cs.uiuc.edu 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.