Arbitrary size data: working with lists

In all of the exercises before we have worked with a single piece of data, whether a number, string, logical value, or an image.

In many problems we need to represent things with a number of values, rather than one. In most of the cases, the order of these values matter. Consider names of students in a course for example. The list grows as new students register, and it rather be kept in alphabetical order in order to, for example, take attendance easily.

Lists in Racket

Let's think about how we keep lists of things. We start off with an empty list, add things to the list (to beginning, middle, or end), or remove things from it (from beginning, middle, or end).

A simple, but important list is the empty list. We can create an empty list (or non-empty list, as we shall see) by using the list creation function list with no parameters:

    (list)

There is also the function empty? to check whether a given list is empty:

    (empty? (list))

Creating lists

We can create a non-empty list by providing the items in the list as parameters to the list function:

    (list 1 2 3)

A list does not have to contain same kinds of values (at least not in Racket!):

    (list 1 2/3 "abc" true)

In fact we can think of lists of lists, since there's nothing to stop us:

    (list 1 "abc" (list 2 3) (square 100 "solid" "black") (list "a" true))

Traversing lists

The computer represents a list as a chain of values, in which every ring of the chain knows a value, and is linked to the rest of the chain. This representation shows itself in how we traverse a list.

A list is traversed by either accessing its first item, or accessing its rest, which is a list and may or may not be empty. The corresponding functions to do these are first and rest:

    (define mylist (list 1 2))
    (first mylist) ;returns 1
    (rest mylist)  ; returns (list 2)
    (first (rest mylist)) ;returns 2
    (rest (rest mylist))  ;returns empty list
    (empty? list)   ;false
    (empty? (rest (rest mylist))) ;true

Example: finding an item in a list using recursion

Now we will write a function to find whether a list contains a particular value. Since lists may contain an arbitrary number of items, they are natural targets for recursive programming.

    (define (find inlist what)
        (cond
            ((empty? inlist) false)
            ((= (first inlist) what) true)
            (else (find (rest inlist) what))))

    (check-expect (find (list) 0) false)
    (check-expect (find (list 1 2 3) 4) false)
    (check-expect (find (list 1 2 3) 1) true)
    (check-expect (find (list 1 2 3) 3) true)

Exercise: Find tail of list

Write a function to return the tail (the last element) of a list. For example, if you name your function as listTail:

    (listTail (list 1 2 3)) ;returns 3

If the list is empty, your function must give an error.

Solution

The solution can be stated as follows in a recursive way:

Translating this formulation into a program:

    (define (listTail list)
        (cond
            ((empty? list) (error "empty list"))
            ((empty? (rest list)) (first list))
            (else (listTail (rest list)))))
    (check-expect (listTail (list 1 2 3)) 3)

Exercise: Finding the length of a list

We will write a function which returns the number of elements in a list. For example:

    (define (listLength list)
        ...)

    (check-expect (listLength (list 1 2 3 4)) 4)

Solution:

Once again, translating problem into a recursive formulation pre-dates the program. Here we can think in the following lines:

Translating this formulation into a program:

    (define (listLength list)
        (cond
            ((empty? list) 0)
            (else (+ 1 (listLength (rest list))))))
    (check-expect (listLength (list)) 0)
    (check-expect (listLength (list 1 2 3)) 3)

Exercise: summing a list of numbers

In this problem you are expected to find the sum of numbers in a list, e.g. (check-expect (sum (list 1 2 3)) 6)

Solution:

    (define (sum list)
        (cond 
            ((empty? list) (error "empty list"))
            ((empty? (rest list)) (first list))
            (else (+ (first list) (sum (rest list))))))
    (check-expect (sum (list 1 2 3)) 6)

Exercise: Find the maximum value in a list of numbers

Given a non-empty list of numbers find the maximum value in the list, e.g (check-expect (maxOf (list 3 2 4 7 6)) 7)

Solution

    (define (maxOf list)
        (cond
            ((empty? list) (error "empty list"))
            ((empty? (rest list)) (first list))
            (else (cond
                    ((> (first list) (maxOf (rest list))) (first list))
                    (else (maxOf (rest list)))))))
    (check-expect (maxOf (list 3 2 4 7 6)) 7)

HOME EXERCISES