Notes for Lecture 4  Tuesday September 14th, 2004
Return to the main StudentFrontPage.
 Scribe = Mike Foss
 Editor =
 Editor =
 Editor =
 Editor =
Contents
See also September14SortInstructions
Administrivia
Add/Drop
Lynn will not be around after about midday tomorrow, but this is ok with Linda. If you have problems with the add/drop process, don't sweat it.
New Problem Set
The beginning of next problem set is posted now.
TA
Katie is a TA for this course! Yay Katie. Look for Katie to answer questions if Lynn is not around.
IM issue
When IMing Lynn, please let Lynn know who you are if your screenname is unrelated to your actual name.
First Half of Higher Order Procedures(to be continued Friday)
One of the properties that make Lisp Lisp is that it treats procedures just like everything else. It also allows you to isolate "environments" and use them later on in code. This is called a continuation. Today, we will explore how to use Lisp's treatment of procedures to create "higher order procedures" which manipulate other procedures.
Comparison
Let us first consider the scenario where we want to take several students and compare their birthdates, sorting them according to this comparison. It might look something like this:
(define sort (lambda (students birthdatecomparer) . . . (if (birthdatecomparer s1 s2) sorting stuff + recursion))
In this execution, we don't actually know how birthdatecomparer works, but we know that it will return a boolean based on the birthdates of the students given. We might write this as:
(define bdaycomparer (lambda (s1 s2) (if (< (bdayof s1) (bdayof s2)) #f #t)))
This is an example of passing procedures in Lisp! In the sort function, we just said that we would need a birthday sorting procedure, but we actually created the procedure elsewhere. So in Lisp, you can pass procedures just as any other type of data. Thus, we can see this in action in the following example:
(sort focs bdaycomparer)
This calls the sort function with our specific implementation of the comparator. Random note: It is not uncommon to see a new lambda expression in the middle of scheme code.
"Mapping," etc. Shown as Higher Order Procedures
Let's look at something we're pretty familiar with now:
(define (incrementall lst) (if (null? lst) '() (cons (+ 1 (car lst)) (incrementall (cdr lst)))))
Thus, incrementall will add one to each element in the given list and return the modified list.
We could also do something else with this list, such as square it:
(define (square lst) (if (null? lst) '() (cons (sqr (car lst)) (square (cdr lst)))))
So as we cdr down the list, we modify the car the same way each time. And by "the same way," I mean that we call the same procedure to work its magic. This is done so often that there is a special function called map which handles this. map looks like this:
(define (map proc lst) (if (null? lst) '() (cons (proc (car lst)) (map proc (cdr lst)))))
So map will automatically cdr down the list for you! It takes the procedure you give it and applies it to the entire list in the same way we've been doing. So now we know another way to write square using our new procedure.
(define square (lambda (lst) (map sqr lst)))
And voila! We have a list with each element squared. There are two other builtin functions like this: filter (which only allows elements which pass some test procedure to be a part of the resulting list; and accumulate. These are 3 higher order procedures in that they manipulate other procedures. The important (big) idea is that we're passing procedures around in order to help break down problems. This is a valid way to process infinite data structures.
Some More Random Notes
Compiled languages have more types than interpreted.
Signal processing extractions are an important way to think about scheme.
We can use the filter paradigm rather than cdr down the list in order to implement a webcrawler.
Trees
What is a Tree?
The abstract data types we have talked about so far are lists, arrays, collections, stacks, & queuesall of which can be represented as a line. Not all data is structured this way, however. For instance, when you retrieve the shtml from a webpage, it is not initially structured as a linear list. For example: (3 + ((2 * 6)  1)) This data structure is called a tree . The following is a better visual way to represent this:
+ /\ 3  /\ * 1 /\ 2 6
Every operation (+, , *) is a node of the tree. Each node may have children, which branch out from the node. If each node has no more than two children, the tree is known as a binary tree. In this case, each node has a left child and a right child. If we want to add the procedures insert, delete, and member? to a tree, we can implement it as a collection. But we need to know this: for any given node, what is its data and what is its children? Sadly, these are three pieces of information (datum, left child, right child) and Lisp is best suited for two pieces of information at a time (because of the basic unit of data, the cons cell). Thus, Lisp is optimized for lists and not trees, but there are still many ways that we might implement a tree. One common way to resolve this is this type of structure (picture it in terms of boxes):
(datum .(leftSubtree .(rightSubtree . ()))) or [datum ]>[leftSubtree ]>[rightSubtree()]
So we can create an abstraction for Lisp to implement the tree data structure. It might consist of the following: (maketree dat L R) ;; output the tree containing these data (node data, left child and right child) (treedatum tree) ;; output the data in the top node of the tree (treeleft tree) ;; output the left subtree of the given tree (treeright tree) ;; output the right subtree of the given tree (leaf? tree) ;; output the boolean whether the given tree is just a leaf (tree? tree) ;; output the boolean whether the given tree is actually a tree
In a structure based language, it may be easier: Tree: data datum; Tree left, right;
If you want to go up the tree, you may need a parent pointer. A nice algorithm exists for garbage collection pointing. A treewalk is very commonly done in a functional style.
Another thing you may want to do with a tree is to print it out in a nice style such as in order traversal. Every time you go down to the left is an open parens, up to the right is a close. The result of such a traversal has this form: (Lchild datum Rchild). Representing the example tree in this form, we have (3 + ((2 * 6)  1)).
Class Exercise
Now we compare three different sorting algorithms:

Bubble Sort 
Insertion Sort 
Selection Sort 

Method 
Start at the beginning of the list and compare the first two elements. If they are in the right order, compare the second element with the third. If the first two are in the wrong order, switch their positions and then compare the second element with the third. Repeat this until you get to the end of the list and then start over. Keep starting over until no one switches places. 
Take the first two elements and compare them. Put them in the right order. Take the third element and it should not follow the second element, compare with the first two until the correct position is found. Then take the fourth element, and so on. 
Start at the beginning of the list and compare the first two elements. Take the higher one and compare to the third element. Take the higher of these and compare to the fourth element until you get to the end of the list. The highest one then takes the first position in the list, and comparison starts between the second and third elements. Continue to compare down the list, and let the highest one take the second position. Repeat. 

Advantages 
This is very easy to implement in code. 
This is quick if the list is already almost in order. 
This gets elements in the right order sooner, and you have a partially sorted list from the beginning 

Disadvantages 
Very resource consuming almost no matter how the list starts 
Very timeconsuming to insert each element. 
Waiting for the whole process to finish (if you don't need just a few elements) is resource consuming 
All of these algorithms are of the order O(n^2).
See also September14SortInstructions
Please add to this page if something is left out, something needs to be clarified, something needs to be pretty, or anything else!