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

From: Gregory Woodhouse (gregory.woodhouse at sbcglobal.net)
Date: Sat Jan 14 18:28:41 EST 2006

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

Posted on the users mailing list.