Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!zaphod.mps.ohio-state.edu!ncar!gatech!taco!cepmax.ncsu.edu!jwb
From: jwb@cepmax.ncsu.edu (John W. Baugh Jr.)
Newsgroups: comp.lang.functional
Subject: Reverse diffs [was Re: functional programming formulation of graph algorithms]
Message-ID: <1991May29.222935.13101@ncsu.edu>
Date: 29 May 91 22:29:35 GMT
References: <TMB.91May29174602@volterra.ai.mit.edu> <5332@ztivax.UUCP> <REDDY.91May28195125@reddy.cs.uiuc.edu>
Sender: news@ncsu.edu (USENET News System)
Reply-To: jwb@cepmax.ncsu.edu
Organization: North Carolina State University
Lines: 19

Thomas M. Breuel writes about "reverse diffs":

> 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)

I've never heard of reverse diffs--could you please give some examples
and/or references.  Also, can reverse diffs deal effectively with
other structured data types (like matrices: constant access & constant
update)?

John Baugh
jwb@cepmax.ncsu.edu