[plt-scheme] Another SICP question (graphs and sharing)

SICP isn't so much about learning to program functionally as it is about 
expanding the way you think about computing. In effect, you're walked 
through the implementation of several languages and run-times; by the 
time you're done, you're ready to go out and develop a language, 
compiler, and hardware for it.

Well, mostly. Kinda. Certainly, if you work through SICP, I expect 
you'll come out changed as a result of the experience.

If you're looking for a more principled/structured introduction 
developing software (that happens to be in Scheme), you might work 
(probably quickly) through HtDP. Then again, perhaps you already looked 
at it, and decided it was too basic.

http://www.htdp.org/

Personally, I found it to be quite enlightening, and generally have 
enjoyed teaching with the text. You might find that FFFK discuss the 
differences between SICP and HtDP, as well as the guiding principles 
behind HtDP, more eloquently than I have:

http://www.ccs.neu.edu/scheme/pubs/fffk-jfp.pdf

As to your questions? I'd say "Is it reasonable?" Maybe. Is there a more 
functional alternative? Certainly. If you look at the Scheme Cookbook, 
you'll see that the functional implementations of basic data structures 
tend to look very much like the structure-derived recipies and templates 
in HtDP:

http://schemecookbook.org/Cookbook/FunctionalQueue

There aren't any examples, I don't think, of graphs in the Cookbook, but 
you might be able to extrapolate from the code you see there.

Unfortunately, I'm not able to speak to how the various garbage 
collectors available to MzScheme deal with sharing. I have my guesses.

HTH,
M

Gregory Woodhouse wrote:
> Another surprise in SICP was the use (again in chapter 3) of set-car!  
> and set-cdr! to implement data structures. It isn't really a surprise  
> that this works, but I thought this sort of thing was frowned upon in  
> functional programming. Is implementing graphs (say) by sharing nodes  
> this way acceptable? I had originally thought of implementing graphs  as 
> a list of edges, each edge being a "pair" of vertices. E.g.,
> 
> ((v (1 2 3)
> ((e ((1 2) (2 3) (3 1))))))
> 
> Although that works, it seems awkward (and potentially inefficient  
> because of all the list traversals). So, is this a reasonable  
> programming technique? Is there a more functional alternative? How  does 
> it (sharing) interact with garbage collection)?
> 
> ===
> Gregory Woodhouse
> gregory.woodhouse at sbcglobal.net
> 
> "Nothing is as powerful than an idea
> whose time has come."
> -- Victor Hugo
> 
> 
> 
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme