Building-up lists

In many problems one needs to traverse a list, and build-up some operating result when doing so. Here we will see some typical examples of how this technique is employed.

Recursion through lists is similar to recursive problems we have seen so far, in the sense that writing the correct program depends on whether you can formulate the problem in a recursive manner.

Generating lists

We have already seen how to consume a list one by one (using first and rest) where the list was created at one (with (list ...), or empty, or equivalently (list)). In this sections we will learn how to build a list one by one, in situations where this is necessary rather than creating the list at once.

The first command we need for this mechanism is cons which stands for construct. cons command takes two arguments: the second is a list (which can be empty or not), and the first is a value to be prepended to the list:

    > (cons 1 empty)
    (list 1)
    > (cons 2 (cons 1 empty))
    (list 2 1)

The other command is append which takes two parameters, both lists, and produces a list which contains all elements from the first list followed by all elements from the second:

    > (append (list 1 2) (list 3 4))
    (list 1 2 3 4)
    > (append empty (cons 1 empty))
    (list 1)

Example: Reversing a list

If we want to reverse a list we must traverse a list while at the same time keep an intermediate list which contains reversed verseion of what we have traversed so far. Thus we want to present the user a function as follows:

    (define (reverseList l)
        ...)

If the list is empty, our task is easy:

    (define (reverseList l)
        (cond
            ((empty? l) empty)
            (else ...)

In ny other case we need to construct a list by appending the first element to the reverse of the last. Since we need to put an element at the end of a list we use append instead of cons here:

    (define (reverseList l)
      (cond
        ((empty? l) empty)
        (else (append 
               (reverseList (rest l)) 
               (list (first l))))))

    (reverseList (list 1 2 3))

Note: a function reverse is already available in Racket which does this.

Example: create a random list

The command (random k) can be used to create to get a random integer in range 1-k. We can use this command to build random lists of any size, for example to test performance of our programs with arbitrarily large input.

In this problem since we can build a list in either from front or at the end, using cons will work:

    (define (makeRandomList n k)
      (cond
        ((or (< n 0) (< k 0)) (error "invalid input"))
        ((= n 0) empty)
        (else (cons (random k) (makeRandomList (- n 1) k)))))

    (makeRandomList 20 1000)

Exercise: Finding reverse list of factorials

In this exercise you are asked to write a function which takes an integer value, \(n\), then returns a list of factorials of numbers from \(n\) downto 1. For example

    (define (factorials n)
        ... )

    (check-expect (factorials 3) (list 6 2 1))

Exercise solution

    ;Function: Number -> list of Number
    ;Takes n and returns a list of factorials (list n! (n-1)! ... 1!))
    (define (factorials n)
        (cond
          ((< n 1) (error "invalid input"))
          ((= n 1) (list 1))
          (else (cons 
                 (* n (first (factorials (- n 1)))) 
                 (factorials (- n 1))))))

    (factorials 3)

Try running the function for a moderate input, e.g. \(n=30\). Note how slow it is? What is the problem?

A better version using helper functions

We can do a much factor computation if we can avoid double-recursion in the function (ie. calling (factorials (- n 1)) twice instead of once). To achieve this we need to write a helper function:

    ;Function Number -> list of Number
    ;takes n and (list(n-1)! ... 1!)), returns (list n! (n-1)! ... 1!))
    (define (prependFactorial n factorialList)
      (cons 
        (* n (first factorialList) )
        factorialList))

    ;Function: Number -> list of Number
    ;Takes n and returns a list of factorials (list n! (n-1)! ... 1!))
    (define (factorials n)
        (cond
          ((< n 1) (error "invalid input"))
          ((= n 1) (list 1))
          (else (prependFactorial n (factorials (- n 1))))))

    (factorials 100)

You can try to run the function with much larger input but it will take time to print the list. So you can try, for example, (length (factorials 1000)) instead.

Example: Find values in list which return true for function

In this exercise you are asked to write a function which takes a list and a logical valued function as parameters (to do this set DrRacket to "Advanced Student" language). The result it returns is a list of values in the given list for which the given function returns true). For example:

    (define (checksTrue list function)
       ... )

    (check-expect (checksTrue (list 1 2 3 4) even?) (list 2 4))

Note that there has been several occasions in which we have passed a function as a parameter to another function.

Solution

    (define (checksTrue list function)
       (cond
         ((empty? list) empty)
         ((function (first list)) (cons 
                                   (first list) 
                                   (checksTrue (rest list) function)))
         (else (checksTrue (rest list) function))))

    (check-expect (checksTrue (list 1 2 3 4) even?) (list 2 4))

Exercise: inserting value to sorted list

Write a function to take a value and a list which is already sorted in ascending order, and return a list which contains the value inserted in proper order. For example:

    (define (insert value list)
        ...)

    (check-expect (insert 3 (list 1 2 5)) (list 1 2 3 5))

Solution

    ;Function number ascending-sorted-list -> sorted-list
    ;Returns a version of the list where the vlue is inserted in proper order
    (define (insert value sortedList)
        (cond
          ((empty? sortedList) (cons value empty))
          ((< value (first sortedList)) (cons value sortedList))
          (else (cons (first sortedList) (insert value (rest sortedList))))))

    (check-expect (insert 3 (list 1 2 5)) (list 1 2 3 5))

Exercise: inserting values to sorted list

In this version of the exercise your function will take two lists, where the latter is sorted, and return a list which contains all numbers from the first list are inserted into the sorted list in proper order. For example:

    (define (insertAll unsortedList sortedList)
        ... )
    (check-expect (insert 3 (list 1 2 5)) (list 1 2 3 5))

Note that you probably need to use the function designed before.

Solution

    ;Function number ascending-sorted-list -> sorted-list
    ;Returns a version of the list where the vlue is inserted in proper order
    (define (insert value list)
        (cond
          ((empty? list) (cons value empty))
          ((< value (first list)) (cons value list))
          (else (cons (first list) (insert value (rest list))))))

    (check-expect (insert 3 (list 1 2 5)) (list 1 2 3 5))

    ;Function list ascending-sorted-list -> sorted-list
    ;returns a list obtained by inserting each of the values in the list into sorted list in proper order
    (define (insertAll unsortedList sortedList)
        (cond
          ((empty? unsortedList) sortedList)
          (else 
           (insertAll 
            (rest unsortedList) 
            (insert (first unsortedList) sortedList)))))

    (check-expect (insertAll (list 6 3 8) (list 1 2 5)) (list 1 2 3 5 6 8))

Meet "Insertion sort"

Congradulations! By building the last two functions you have almost implemented a program which can sort an unsorted list. The algorithm is called insertion sort. We will just add a small function to combine the pieces:

    (define (insertionSorter unsortedList)
        (insertAll unsortedList empty))

    (check-expect (insertionSorter (list 2 3 1)) (list 1 2 3))

The insertion sort is not the best algorithm for sorting values. Try to find out how many operations it takes to sort a list of size \(n\).

Example: Animation with multiple balls

In this animation we will create a universe which contains two or more moving balls instead of just one. This requires (1)rebuilding a list of balls at each tick, and (2)building the image of the world by placing each ball one by one on the scene.

This example requires us to use lists of structures, and construct them with cons:

    (define animationSizeX 400)
    (define animationSizeY 400)

    (define-struct Point (x y))
    (define-struct Velocity (x y))
    (define-struct Ball (radius point velocity color)) 

    ;add velocity to point
    (define (addVelocityToPosition position velocity)
      (make-Point (+ (Point-x position) (Velocity-x velocity)) (+ (Point-y position) (Velocity-y velocity))))

    ;negate X component of velocity
    (define (negateX velocity)
      (make-Velocity (- (Velocity-x velocity)) (Velocity-y velocity)))

    ;negate Y component of velocity
    (define (negateY velocity)
      (make-Velocity (Velocity-x velocity) (- (Velocity-y velocity))))

    ;a helper function to decide if number x is between y and z
    (define (between? x y z)
      (and (<= x z) (>= x y)))

    (define initialState (list
                          (make-Ball 20 (make-Point 1 1) (make-Velocity 15 25) "green")
                          (make-Ball 30 (make-Point 100 1) (make-Velocity 25 15) "red")))

    ;changes the whole world by rebuilding balls list (the worldState) by changed balls
    (define (changeWorld worldState)
      (cond
        ((empty? worldState) empty)
        (else (cons (changeBall (first worldState)) (changeWorld (rest worldState))))))

    ;Changes a single ball
    (define (changeBall ballState)
          (cond 
            ((not (between? (Point-x (Ball-point ballState)) 0 animationSizeX)) 
             (make-Ball 
              (Ball-radius ballState)
              (addVelocityToPosition (Ball-point ballState) (negateX (Ball-velocity ballState)))
              (negateX (Ball-velocity ballState))
              (Ball-color ballState)))
            ((not (between? (Point-y (Ball-point ballState)) 0 animationSizeY)) 
             (make-Ball 
              (Ball-radius ballState)
              (addVelocityToPosition (Ball-point ballState) (negateY (Ball-velocity ballState)))
              (negateY (Ball-velocity ballState))
              (Ball-color ballState)))
            (else
             (make-Ball 
              (Ball-radius ballState)
              (addVelocityToPosition (Ball-point ballState) (Ball-velocity ballState))
              (Ball-velocity ballState)
              (Ball-color ballState)))))


    ;draws the world by placing ball images on top of one another
    (define (drawFrame worldState)
      (cond
        ((empty? worldState) (empty-scene animationSizeX animationSizeY))
        (else (drawBall (first worldState) (drawFrame (rest worldState))))))

    ;Draws a ball on top of onWhat, the existing scene
    (define (drawBall ballState onWhat)
         (place-image 
              (circle (Ball-radius ballState) "solid" (Ball-color ballState))
              (Point-x (Ball-point ballState)) (Point-y (Ball-point ballState))
              onWhat))

    ;A simple function to react to mouse clicks,
    ;by resetting ball position
    (define (handleMouseClick worldState x y event)
       (cond
            ((string=? event "button-down") initialState);reset worldState
            (else worldState)))  ;do nothing

    (big-bang initialState
                  (on-draw drawFrame)
                  (on-tick changeWorld)
                  (on-mouse handleMouseClick))