SE250:lab-4:jsmi233

Task one

I wrote this code:

 int length(Cons* list) {
     int count = 0;
     for (; list != nil; list = list->tail)
 	count++;
     return 0; //later I realised I should return count.. duh!
 }

It looks like it should work for an empty list and a non-empty list.

Task two

Firstly I wrote this:

 element_t first(Cons* list) {
     int count = 0;
     for (; list != nil; list = list->tail)
 	if (++count == 1)
 	    return list->head;
     return 0;
 }

Then I realised that since I will be writing a second, third, and fourth function, I might as well make a generalised function that works for all four functions and save some code. I called my generalised function elementAt:

 element_t elementAt(Cons* list, int index) {
     int count = 0;
     for (; list != nil; list = list->tail)
 	if (++count == index)
 	    return list->head;
     return 0;
 }

Then it occurred to me that returning zero might fail if later the type element_t was changed. So I instead returned NILL->head. I also decided to make the list index zero based. So elementAt now looks like:

 element_t elementAt(Cons* list, int index) {
     int count = 0;
     for (; list != nil; list = list->tail)
 	if (count++ == index)
 	    return list->head;
     return NILL->head;
 }

And so my first.. fourth functions are these:

 element_t first(Cons* list) {
     return elementAt(0);
 }
 
 element_t second(Cons* list) {
     return elementAt(1);
 }
 
 element_t third(Cons* list) {
     return elementAt(2);
 }
 
 element_t fourth(Cons* list) {
     return elementAt(3);
 }
 

Task three

It seems that I have already accomplished task three by writing my elementAt function. I just spotted a bug in my first.. fourth functions, their call to elementAt (now renamed to nth) doesn’t pass the list.

Having fixed this, I move to task four.

Task four

Here is my code:

 int equal(Cons* list1, Cons* list2) {
     for (; list1 != nil && list2 != nil; list1 = list1->tail, list2 = list2->tail)
 	if (list1->head != list2->head)
 	    return FALSE;
     return list1->head == list2->head;
 }

Task five

While I was writing my code John Hamer noticed my use of NIL and suggested that I should be using nil. I don’t understand how the declaration of NIL works: static Cons NIL = { 0, &NIL };

How can you have a global static variable??

Here is my find function:

 Cons* find(element_t value, Cons* list) {
     for (; list != nil; list = list->tail)
 	if (list->head == value)
 	    return list->head;
     return nil;
 }

Task six

This is a bit more difficult to imagine, I might resort to pen and paper.

Ok, I got away with doing my working in the comments. Here is my code:

 Cons* copy_list(Cons* list) {
     Cons* start = list;
     Cons* temp = nil, copy = nil;
     for (; list != nil; list = list->tail)
 	temp = cons(list->head, temp);
     for (; temp != nil; temp = temp->tail)
 	copy = cons(temp->head, copy);
     
     // temp = last, ..., second, first, nil
     // copy = first, second, ..., last, nil
 
     return copy;
 }

I know I have just lost temp in the memory somewhere, but I am too lazy right now to do anything about that.

Task seven

I think I now understand what the handout means by length(xs). Here is my function:

 Cons* append(Cons* xs, Cons* ys) {
     int len = length(xs) + length(ys);
     Cons* list2 = nil, iterator;
     int i;
     for (int i = 0; i < len; i++) {
 	list2 = cons(0, nil);
     }
     iterator = list2;
     for (; xs != nil; xs = xs->tail, iterator = iterator->tail) {
 	iterator->head = xs->head;
     }
     for (; ys != nil; ys = ys->tail, iterator = iterator->tail) {
 	iterator->head = ys->head;
     }
     return list2;
 }

Task Eight

This looks easy.

Here is my code:

 Cons* nappend(Cons* xs, Cons* ys) {
     Cons* iterator;
     if (xs == nil)
 	return ys;
     for (; iterator->tail != nil; iterator = iterator->tail);
     iterator->tail = ys;
     return xs;
 }