[plt-scheme] self-referential data structures

On Mar 5, 2009, at 5:10 PM, aditya shukla wrote:

> Here in chapter 9 the problem of adding all numbers of a list of  
> numbers is explained.The method explained to tackle the problem is  
> based on the data definition of list of numbers .And this has been  
> the approach of the book that is a problem is solved according to  
> the data definition of a data structure.Suppose I switch from  
> scheme to any other programming language say c++ ,so should the  
> same approach should be followed ?

I have taught this exact same data structure, and the exact same  
approach to solving the problem, in Java and C++.  It's more  
complicated in Java, and even more complicated in C++, but it can be  
done.  In fact, I assigned my beginning Java students to do that  
exact problem yesterday.

In partial answer to your previous question, no, self-referential  
data types are not limited to functional programming, and in fact  
people have been building lists and trees in C, Pascal, Ada, C++,  
etc. for decades.  Some of the problems they encounter can be  
eliminated by making the data structures "immutable", i.e. creating a  
little safe island of functional programming within the terrifying  
ocean of mutation and imperativity. :-)  In Java and C++, for  
example, you can largely achieve this by providing getters, but no  
setters, for your class fields.

However, there are more complicated self-referential data types that  
are difficult to do without mutation.  For example, consider
(define biglist (list 10 9 8 7 6 5 4 3 2 1 0))
(define partlist (rest (rest (rest (rest biglist)))))
 From "partlist", you can easily get the 5th element of the original  
list, or move forward to the the 6th element and so on... but there's  
no way to "move backward" through the original list to see the 3rd  
element of the original list, because "partlist" doesn't contain that  
information.  For some applications it's very useful to be able to  
move both backward and forward through a large list, and the usual  
data structure to do that is called a "doubly linked list".  Since  
the 5th element of a list has to "know" about both the 4th and 6th  
elements, both of which have to "know" about the 5th, the usual way  
to build a doubly linked list is to create the 6th element, then  
create the 5th element referring to it, then MUTATE the 6th element  
so that it knows about the 5th element in turn, then create the 4th  
element referring to the 5th element, then MUTATE the 5th element so   
it knows about the 4th element, and so  on.  This is difficult to do  
without mutation.

However, if you basically like functional programming but need a  
doubly-linked list for one part of your program, you can wrap up the  
mutating doubly-linked list in a "front end" that looks functional,  
even though there's actually some mutation going on behind the scenes.



Stephen Bloch
sbloch at adelphi.edu