List Homework

September 7, 2018

We’ve done these before, but it doesn’t hurt to do them again. First, a simple recursive version of the list-length program:

(define (len xs)
  (if (null? xs) 0
    (+ (len (cdr xs)) 1)))

> (len '(1 2 3 4 5))
5

That works, but it’s not tail recursive, because len isn’t in tail position (it is inside the call to +), so the function operates in linear time and space; here is a better version:

(define (len-aux xs len)
  (if (null? xs) len
    (len-aux (cdr xs) (+ len 1))))

(define (len xs) (len-aux xs 0))

> (len '(1 2 3 4 5))
5

Now len-aux is in tail position; the function operates in linear time and constant space. Here we reverse a list, using a tail recursive function:

(define (rev-aux xs zs)
  (if (null? xs) zs
    (rev-aux (cdr xs) (cons (car xs) zs))))

(define (rev xs) (rev-aux xs '()))

> (rev '(1 2 3 4 5))
(5 4 3 2 1)

You can run the program at https://ideone.com/x46jpU.

Advertisements

Pages: 1 2

One Response to “List Homework”

  1. Daniel said

    Here’s a solution in C.

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node {
        int value;
        struct node* next;
    } node_t;
    
    void reverse(node_t** list) {
        node_t* prev = NULL;
        node_t* node = NULL;
        node_t* next = *list;
        while (next != NULL) {
            prev = node;
            node = next;
            next = next->next;
            node->next = prev;
        }
        *list = node;
    }
    
    size_t length(node_t* list) {
        size_t result = 0;
        node_t* node = list;
        while (node != NULL) {
            ++result;
            node = node->next;
        }
        return result;
    }
    
    void print_list(node_t* list) {
        node_t* node = list;
        printf("{");
        while (node != NULL) {
            printf("%d", node->value);
            node = node->next;
            if (node) printf("->");
        }
        printf("}");
    }
    
    int main(int argc, char* argv[]) {
        node_t* list = NULL;
        for (int i = argc - 1; i > 0; --i) {
            node_t* node = (node_t*)malloc(sizeof(node_t));
            node->next = list;
            node->value = atoi(argv[i]);
            list = node;
        }
        printf("list:\n  ");
        print_list(list);
        printf("\n");
        size_t len = length(list);
        printf("len(list):\n  %zu\n", len);
        reverse(&list);
        printf("reverse(list):\n  ");
        print_list(list);
        printf("\n");
        node_t* node = list;
        while (node != NULL) {
            node_t* next = node->next;
            free(node);
            node = next;
        }
        return EXIT_SUCCESS;
    }
    

    Example Usage:

    $ ./a.out {1..10}
    list:
      {1->2->3->4->5->6->7->8->9->10}
    len(list):
      10
    reverse(list):
      {10->9->8->7->6->5->4->3->2->1}
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: