Immutable Lists and Algorithms on Them

In this lab, we will build immutable lists (lists that can't be changed once they are made) and explore the algorithms we can write to process the data that they hold.

First, recall our definition of a list:

A List is an abstract container of objects:

• An Empty list is a List and has no data,
• A Non-Empty list is a List, and has a data element, called first, and has another List, called rest.

This definition is independent of whatever programming language we might use to implement it. It is strictly our abstract definition of a "list". The golden rule here is

Your code should always match your abstractions as closely as possible.

Looking at the above definition of a list, we see two things:

1. An Empty list is a List and likewise, a Non-Empty list is a List.
2. A Non-Empty list has two elements, one of which is a list which is most notably, the abstract list, not one of concrete subtypes.

These two observations map directly to our OO modeling notions of inheritance and composition. Thus we can immediately draw a UML diagram corresponding to our definition:

.

Notice that we have used an interface to represent the abstract list, as interfaces are commonly used to represent the pure abstract behaviors such as in a list.

This lab uses Full Java language level.

Let's go through a series of exercises to build our list system and to endow it with some processing capabilities.  Note that the completion of these exercises is required for HW05:

Exercise #1 -- Make the list:

Before we make rabbit stew, we must first catch the rabbit....

1. Create a "lab05" directory.
2. Inside the lab05directory, make a subdirectory called "lab05ex1" with the usual "src" and "classes" subdirectories.
3. In the src directory, create a subdirectory (package) called "listFW" ("list FrameWork").
4. Start up DrJava and create a lab05ex1 project that with the build directory set for the classes directory.
5. Using the above UML diagram, create three .java files, one for each class/interface above. Each class or interface should be in the listFW package, i.e. saved in that directory and with the line package listFW; at the top of the Java file.

Next, we need to test what we have so we can be confident that the basic structure is set up correctly:

1. Create a test class for IList called Test_IList.   Put test classes in their own package inside the package being tested:
   1. Put the line package listFW.test; at the top of the Java file.
   2. Right below that line, put the line import listFW.*;  to tell the compiler to use recognize all names of classes in the listFW package.
   3. Save the Java file into a new subdirectory of listFW, ie. \lab05\src\listFW\test.  
2. There's not much to test yet, but we can test that we can instantiate the various concrete subclasses. Write a test method that simply instantiates an MTList and use System.out.println to print out something that indicates that the instantiation worked, such as "My list is "+myEmptyList.toString(). Remember that all Objects have a toString method that by default, returns something that has the type of the object plus a unique identifying number (its "hashcode").
3. Run your test. If it doesn't work, stop and back up.
4. Write another test method that does the same for NEList.
5. Run your tests.
6. Realize that you just wrote essentially the same code twice, so write a private method called printObject that takes an Object as an input and returns a boolean value.
   1. This method contains the System.out.println call you had in your other methods.
   2. The return value should simply be "true".
   3. Remove the println's from the rest of your code and replace them with a call to printObject. The result of this call should be passed to a call to assertTrue.
7. Run your tests again.
8. Write a third test method that tests the polymorphic capabilities of IList. This method should
   1. Define a local variable of type IList which is initialized to an MTList.
   2. Using assertTrue and printObject as before, print this list to the screen.
   3. The same IList variable should then be assigned to a new instance of NEList.
   4. Repeat the previous code to print the list to the screen.
9. Run your tests again. Are the results as you expected them to be?

The code for this point of the lab can be downloaded here (no peeking!!).

OK, so far so good.

Exercise #2 -- Building a list.

Make a copy of your lab05ex1  directory and rename it "lab05ex2". You'll want to rename your project as well. 

Now let's try to build a list up.

1. First, let's recognize that there is only one empty list in the world, so let's make the MTList into a singleton:
   1. Create a private no-parameter constructor for MTList. This constructor does nothing (but it does it very well!).
   2. Create a public, static and final field of type MTList called Singleton that is initialized to a new MTList instance.
2. Run your test code again.
   1. Didn't work did it? Why not?
   2. Fix how the test code that instantiates the MTList object.
   3. Keep trying until your test code works again.
3. Oops. We have a problem. NEList has fields, but we have no way yet to initialize them. So, first write a public constructor for NEList that takes in the two parameters necessary to initialize its two fields.
4. OK. Now run your tests again.
   1. They don't work? Why not?
   2. To instantiate a non-empty list requires another list! It also requires an object to put into first.
      1. Strings are simple objects that are easy to deal with. We'll put Strings into first for now.
      2. Change the instantiation of the NEList in your test code so that its constructor takes a String, such as "a", and the empty list, MTList.Singleton.
      3. Run your tests again, correcting your code until they run correctly.
5. Let's now try it with a longer list:
   1. Add another 2 lines to your IList test method to instantiate and print a longer list. Do not delete the code you already have, as it tests a short list!
   2. Remember that an object does not have to be assigned to a variable to be used. For instance, the following is perfectly valid: new NEList("a", new NEList("b", MTList.Singleton))
   3. Run your tests. Do we need to test an even longer list? Why not?

Why didn't our tests ever print the elements in our list?

The code for this point of the lab can be downloaded here (no peeking!!).

Exercise #3 -- A simple toString algorithm

Since the rest of the exercises, constitute part of your homework, copy your lab05ex2 directory and rename it "lab05HW05".  You may do the rest of the exercises in this one directory.

To get a look at what inside our list, let's override the toString method inherited from Object. This method returns a string representation of the object. We'll write something simple first and then later, when we learn a some better techniques, we'll fix it up to be much nicer.

The toString method has the following signature (the description of the name of the method, its return value and the types of its input parameters):

public String toString()

1. Add this method to MTList and NEList. Why doesn't it need to be added to IList?
2. What sort of string should the empty list return as its string representation?
3. For the NEList, how does the string representations of the list relate to the string representations of its first and rest?

Note: There is more than one "solution" to this problem--it all depends on what you consider is the "right" string representation.

Run your tests again. Did you get the results you wanted?

The toString method is an example of a recursive algorithm. If you look at the code in the NEList, you see that the result of toString is determined (partially) by the result of toString being called on rest. It almost looks like toString calls itself since it calls a method of the same name, but it does not because the toString being called is that of a different object. That is, the recursive call is to _rest.toString() not to this.toString(). Recursive algorithms in OOP are actually examples of delegation.

How does the algorithm ever end you ask? Well, at some point, the list is an empty list. The toString of the empty list does not need to call anything else, as the empty list knows the answer unequivocally. The algorithm thus progresses no further and each call starts to return to its caller.

The key issue here is that an abstract list "knows" how to calculate the product of its elements. The concrete implementations of the abstract list each knows how to calculate the product for themselves, without worrying about the other. Notice that the MTList code has no references to NEList and vice versa. The algorithm never has to check whether the list is empty or not because each kind of list knows exactly what to do.

All recursive algorithms are characterized by having two parts:

1. Base case: This is the situation where the answer is calculable in an unequivocal manner. That is, no other objects need to be consulted. In a list, the empty list is the base case.
2. Inductive case: This is the situation where the answer depends on the result from a delegation to another object. In a list, non-empty list is the inductive case.

Notice that the code written is exactly the same as the play-acted process! This is what we mean by "expressing your abstraction directly in code".

Modify your test code such that it actually test that toString returns the correct result. You will want to remove the System.out.println statements.

Exercise #4 -- The Product of All the Elements

First, a bit of play-acting:

1. Gather 4 or 5 of your classmates around and get as many pieces of paper.
2. On one or two of those pieces of paper, write "You are an Empty list".
3. On the remaining pieces of paper, write "You are a Non-Empty List. Your first is [some number] and your rest is [one of your classmates]."
4. Do not let anyone know who is is empty or non-empty.   All anyone knows is that there are ILists with a getProduct() method.
5. Randomly show, do not hand out,  the papers, one to a student.
6. Randomly pick one of your classmates and ask him/her, "What is the product of all the elements in the list?".
   1. If the person is an empty list, what should their answer be? Think about what is the value of 0!.
   2. If the person is a non-empty list, what should they do?
   3. Is there anything more that needs to be specified in order to calculate the product of all the elements of a list?

Now, implement the above process in code. Proceed along the lines that your wrote the toString method above.

Notice how the algorithm follows this process (assume a non-empty list here):

1. Ask the rest for the product of the rest of the list (inductive case).
   1. A non-empty rest does 1) again (inductive case).
   2. An empty rest simply returns its result (base case).
2. The recursive result is then multiplied with first and the result is returned.

What we see is that the inductive case is characterized by waiting for its rest to return its result so that it can finish its own calculation. We refer to this as "pending operations". As the recursion unrolls towards the base case, each inductive case encountered enters a pending operation state. By the time the base case is reached, every non-empty list object involved has a pending operation, waiting for a result to be returned to them. When the base case finally returns the result, the pending calls resume one by one and the recursion rolls back out to the beginning of the list.

The result is first returned by the base case, and then the inductive case takes that result and calculates its result. If one were to take a bird's eye view of the process on the whole list, one would see the result accumulating from the back of the list (the empty list) towards the front of the list (non-empty list). We like to call this "reverse accumulation" since the result is accumulated as the algorithm "reverses" its way back out of the list.

But the key to understanding recursion is not to try to see the whole list at once. Recursion is a very locally defined process, that is, the base case is defined a doing something and the inductive case is defined as doing something else. All that is required is that the inductive case call the next element in the chain of objects (and the base case does not) and the process will work. One does not need to know what kind of object the next (i.e rest) is, nor how long the total chain is, just that the next object has the necessary abstract behavior. One never needs and quite frankly, never should, think about the process over the whole data structure. The beauty of recursion is that it reduces the processing of very complex data structures down to very simple, unrelated operations.

Here are some hints on how to deal with int when your system wants Object:

• When you save an int in a NEList, it is automatically "boxed" ("autoboxed") and saved as an Integer which is an Object, which is fine, polymorphically. The problem comes when you try to use _first, which is not an Integer. But since you know that it really is an Integer object, you can perform a "downcast".
  • To do a downcast, we write (Integer) _first. This tells the compiler that _first really is an Integer (Java actually doesn't trust you and checks to make sure).

Add a test method to your Test_IList test class to test that your algorithm produces the correct result.

Exercise #5: Summing the Elements of a List.

Write the reverse accumulation algorithm that will return the sum of all the elements of a list.

Add a test method to your Test_IList test class to test that your algorithm produces the correct result.

Exercise #6: Copy a List.

This is a different twist on a reverse accumulation algorithm. Write an algorithm that will return a copy of the list. That is, the result is a new list with the same values in first if the list is non-empty. The empty list is a singleton, so the issue is moot there.

If you're not sure what to do, read the statement of the problem above very carefully and then write down, in Java, exactly what the algorithm is. Don't try to "figure out how to do it"--just write down what the problem says it is.

Add a test method to your Test_IList test class to test that your algorithm produces the correct result.

Exercise #7 -- Another Way to Add

Reverse accumulation algorithms work very nicely but are admittedly not always the most intuitive algorithm. When one is faced with a list of numbers, do we naturally add the numbers from the bottom to the top? Or do we add them from the top to the bottom, accumulating an answer as we move forward through the list? If that's the way that we view the problem, then we should write exactly that in code.

First, let's try some play-acting to see what exactly is going on:

1. Make a "list" of people as done before.
2. When asked for the sum,
   1. An empty list returns zero as always.
   2. A non-empty list, takes its first and hands it to its rest to be added to its sum. The rest will return the total sum.
      1. An empty list will return the value given to it.
      2. A non-empty list will add its first to the given value and then hand that sum to its rest, which will repeat step b.i or b.ii. The result from the rest will be returned.

Things to note about this forward accumulation algorithm:

• The operation that the list does initially, is not the same as any subsequent operations.
  • The empty list has two different possible behaviors, depending on whether it was the initial call or not.
  • Likewise the non-empty list has two different possible behaviors.
    • The initial call to a non-empty list is not recursive! This is because the call to rest is not to the same method as was originally called by the user of the list. The behavior of rest is not the same as the list itself!
    • The subsequent operations by a non-empty list are recursive because they do the same thing over and over again until the base case (empty list) is reached.
  • The result is fully calculated by the time the empty list is encountered. All that has to happen then is that the result is passed, unmodified back up the list. This is called "tail recursive".

What does this tell us? It tells us that an IList has two methods used to add using a forward accumulation algorithm.

1. The method that is called initially. This non-recursive method simply gets the process going. It initializes the accumulation.
2. The method that is called subsequently. This recursive method accumulates the result, passing it forward each time if it is non-empty or simply returning it if it is empty. This method is often called the "helper" method and is often named as such, e.g. getMult_help.

Add a test method to your Test_IList test class to test that your algorithm produces the correct result.

Exercise #8 -- Another Way to Multiply

Write a forward accumulation algorithm to multiply all the elements of a list together and return the result.

Add a test method to your Test_IList test class to test that your algorithm produces the correct result.

Exercise #9 -- Reverse a List

Write a forward accumulation algorithm to return a new list with all the same elements as the original list, but in reverse order.

Compare this algorithm tot he reverse accumulation copy algorithm.

Can reverse even be written using reverse accumulation?

Add a test method to your Test_IList test class to test that your algorithm produces the correct result.

Exercise #10 -- a better toString

We wrote a simple toString method above, but the output, while "correct" wasn't exactly pretty or intuitive. For instance, what if we had this list, ("ab", "c", "de")? The output would be a rather confusing "abcde". What we want is an output that looks like we expect it to look, that is, something more like "(ab, c, de)" with commas and parentheses.

In order to be able to express the problem, we must first understand it. We must learn to express the obviousness about it. Let's see how we can look at empty and non-empty lists respectively:

Last Revised Thursday, 03-Jun-2010 09:50:27 CDT

©2008 Stephen Wong and Dung Nguyen