Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!uunet!lll-winken!sun-barr!ccut!s.u-tokyo!riksun!rknss1!rkna50!nttlab!icot32!hitgw!harl86!kondoh
From: kondoh@harl86.harl.hitachi.co.jp (Hidetaka KONDOH)
Newsgroups: comp.lang.functional
Subject: Re: Summary: functional programming of graph algorithms (long)
Message-ID: <1865@harl86.harl.hitachi.co.jp>
Date: 20 Jun 91 03:01:47 GMT
References: <5495@ztivax.UUCP>
Organization: Advanced Research Laboratory, Hitachi, Ltd.
Lines: 72
In-reply-to: corvara@ztivax.UUCP's message of 11 Jun 91 14:07:46 GMT
Return-Receipt-To: kondoh@harl.hitachi.co.jp
CC: kondoh



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

   >> Here is my summary of responses on functional programming of graph algorithms.
   >> To remind you, in article <5332@ztivax.UUCP> I wrote:
   >> 
   >> > 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."
   >> > 
   >> > When I tried to write down a purely functional formulation of some
   >> > manipulations on binary decision diagrams I found that indeed to be
   >> > quite a difficult and unnatural task. Are there really fundamental
   >> > reasons for these difficulties to arise or is my vision and understanding
   >> > of graph algorithms just too imperative? Are there any published attempts
   >> > to give functional formulations of graph algorithms? Any opinions from
   >> > netland?

Here is another paper discussing the way to formulate graph algorithms
using a lazy functional language (Haskell) in fairly general setting:

	Yugo Kashiwagi & David S. Wise
	    "Graph Algorithms in a Lazy Functional Programming Language"
		Technical Report No. 330, Computer Science Dept.,
		Indiana University (April, 1991).

And here I quote its abstract:

	   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 progamming avoids them, but it 
	also preludes known algorithms that are uniprocessor-optimal.
	   Functional programming provides another, translation scheme that 
	computesthe fixed point without relying on the operational concept 
	of "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.

This paper might give the very just answer to your initial question 
and can be easily obtained through the report secretary of the department.

The e-mail address of the first author is: 
	kasiwagi@hcrlgw.crl.hitachi.co.jp


And here is another paper relating your question:

	F. Warren Burton & Hsi-Kai Yang
	    "Manipulating Multilinked Data Structures in a Pure Functional 
	     Language", Software Practice-Experience, Vol. 20, No. 11,
	     1167-1185 (November, 1990).

This paper collects case studies of description of graph-like data 
structures in functional setting.

--
Hidetaka KONDOH (kondoh@harl.hitachi.co.jp)	Advanced Research Laboratory
						Hitachi, Ltd.
Voice: +81-492-96-6111/6112 (Ext. 6328)		Hatoyama, Saitama  350-03
Fax:   +81-492-96-6005				JAPAN
-- 
Hidetaka KONDOH (kondoh@harl.hitachi.co.jp)	Advanced Research Laboratory
						Hitachi, Ltd.
Voice: +81-492-96-6111/6112 (Ext. 6328)		Hatoyama, Saitama  350-03
Fax:   +81-492-96-6005				JAPAN