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

======= At 2006-01-14, 16:28:41 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)?

Scheme is not pure functional. Nor does SICP. Both method are accept-
able. http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf has more discussion
about pure functional data structures. 

For GC: if sharing is not available, GC can be implemented by reference 
counting. Otherwise, pure reference counting won't work.


>
>===
>Gregory Woodhouse
>gregory.woodhouse at sbcglobal.net
>
>"Nothing is as powerful than an idea
>whose time has come."
>-- Victor Hugo
>