Comp 200 Lecture
Lists

The explorer at the red-blue island (finish).

A list-of-numbers is either

• empty,
or
• (cons number list-of-numbers)

(Note that you type the part in this font verbatim, while the part written in this font is to be replaced with specific instances.)

1. First we'd better write down some examples of list-of-numbers. Following the above definition, what is a list of length 0? Of length 1? Length 2? We'll use these lists again later (as test cases), so let's give them names. Fill in the dot-dot-dots:

   (define len0 ...)
   (define len1 ...)
   (define len2 ...)
   (define len3 ...)
   

2. Okay, now let's make a function "my-sum", which takes in a list-of-numbers (a list of any length!), and returns a number: namely, the sum everything in the list-of-numbers. That is, we want:

   (my-sum (cons 3 (cons 5 empty))) = 8
   (my-sum (cons 1 (cons 3 (cons 5 empty)))) = 9
   (my-sum (cons 7 empty)) = 7
   (my-sum empty) =    ;;;  Discuss!
   
   
   (my-sum len0) = 0
   (my-sum len2) = 
   (my-sum (cons 7 (cons 6 (cons 5 (cons 4 (cons 3 (cons 2 (cons 1)))))))) = 28
   

   Goodness, how will we make a function which handles any list-of-numbers?
3. We'll start by just writing a comment to keep us on-track.

   ;; (my-sum nums): (list-of number) --> number
   ;; Return the sum of the numbers in the list we call "nums".
   ;;
   

4. Write the define for a function which will take one argument called nums.

   ;; my-sum: a function taking a list-of-numbers "nums",
   ;; and return a number (the sum of everything inside nums).
   ;;
   (define (my-sum nums)
        ...))
   

5. Our definition said there were two sorts of list: empty, and those made by cons. So our function should distinguish between these two cases (and no more): We'll use the built-in function empty?, which takes a list and returns true/false, depending on whether it's empty or not.

   ;; (my-sum nums):   (list-of numbers) --> number
   ;; Return the sum of all the numbers inside nums.
   ;;
   (define (my-sum nums)
        (if (empty? nums)
            ...
            ...))
   

   Now we just need to fill in the ...s :-).
6. If we have an empty list, what should my-sum return?

   ;; (my-sum nums):   (list-of numbers) --> number
   ;; Return the sum of all the numbers inside nums.
   ;;
   (define (my-sum nums)
        (if (empty? nums)
            0
            ...))
   

7. If nums isn't empty, that from our definition nums must be of the form (cons num lon), where lon is a list-of-numbers. Another baby-step: Before doing anything fancy, let's just extract those sub-parts of nums. How do you extract sub-parts of something built via cons? Yep -- first, rest!

   ;; (my-sum nums):   (list-of numbers) --> number
   ;; Return the sum of all the numbers inside nums.
   ;;
   (define (my-sum nums)
        (if (empty? nums)
            0
            ...(first nums)...(rest nums)...))
   

   We've simplified our program to just wondering, how do we combind the first number and the rest of the list, to get the sum of the original list?
8. Okay, here's the mind-bending step: We know that (rest nums) is a list-of-numbers. What function can we call on a list-of-numbers? my-sum itself!?!

   ;; (my-sum nums):   (list-of numbers) --> number
   ;; Return the sum of all the numbers inside nums.
   ;;
   (define (my-sum nums)
        (if (empty? nums)
            0
            ...(first nums)...(my-sum (rest nums))...))
   

   This is weird.
9. What sort of value is (first nums) -- a symbol, a number, a boolean, a list? Likewise, What sort of value is (my-sum (rest nums)) -- a symbol, a number, a boolean, a list? Ask a labbie if unsure. (Hint -- it's not a list. (rest nums) is a list, but not (my-sum (rest nums)). In fact, what sort of value does my-sum always return?)
10. But for a moment, hold your doubt in abeyance, and suppose that (my-sum (rest nums)) will indeed correctly return the sum of the (rest nums). Then our question becomes:
    If we're handed the numbers (first nums) and the sum of (rest nums), how do we put them together to get the sum of the whole list?

    ;; (my-sum nums):   (list-of numbers) --> number
    ;; Return the sum of all the numbers inside nums.
    ;;
    (define (my-sum nums)
         (if (empty? nums)
             0
             (+ (first nums) (my-sum (rest nums)))))
    

11. Does this really work? Let's try it out. Type the following into the top half of drscheme, and press execute. Then inspect the answers closely, for correctness.

    (my-sum (cons 3 (cons 5 empty)))
    (my-sum (cons 1 (cons 3 (cons 5 empty))))
    (my-sum (cons 7 empty))
    (my-sum empty)
    
    
    (my-sum len0)
    (my-sum len2)
    (my-sum (cons 7 (cons 6 (cons 5 (cons 4 (cons 3 (cons 2 (cons 1))))))))
    

12. Finally, to internalize what's going on, use the stepper. Keep yourself thinking, but telling your partner what's going to happen on each click of the stepper.

1. Write the function my-length, which takes in a list-of-numbers, and returns its length. Do this by following the above recipe step-by-step! You'll find most of the steps for this problem are virtually identical to the steps for the previous problem. In fact, the only step that's truly different is the one

   If we're handed the numbers (first nums) and the length of (rest nums), how do we put them together to get the sum of the whole list?

2. Here's an example that is extremely like sum from above. Write product, which takes a list of numbers and returns the product of all the numbers in the list. Again, go through the same sequence of steps as you did for sum. You may want to step through in your head what happens for a list of length one. If you followed the above steps, your program will handle any list, including the empty list. What is a reasonable idea of the product of no numbers at all?
3. Write max, which returns the largest number in a non-empty list of numbers. (It doesn't make sense to ask about (max empty).) This will still follow the above pattern, except that instead of having the "base case" be empty, it is a list of exactly one number. So first you have a sub-problem: how can you tell if a list has exactly one element in it?
   Hint: Also write another helper function max-of-2, which takes in exactly two numbers.

1. First, write down the function header:
   1. comments about what the function takes in and returns. For example,
      ; (our-function nums) : list-of-numbers --> symbol
   2. what it returns (answer ``what'', not ``how''). Continuing the silly example:
      

      ; return 'has-17 if 17 is one of the numbers inside nums
      ; or 'no-17 if nums doesn't contain a 17.
      

   3. the define (a bit of actual code),
      (define (our-function nums) ...).
      We'll fill in the ... later.
2. Test cases:
   1. Write down some examples of the input data -- e.g., some List-of-Numbers.
      empty
(cons 3 (cons 7 empty))
(cons 3 (cons 17 empty))
   2. Now expand these into test cases, by actually calling the function on them: below the header/skeleton you just wrote.
      (our-function empty) = false
(our-function (cons 3 (cons 7 empty))) = false
(our-function (cons 3 (cons 17 empty))) = true
3. Now some more rote work on the ... we left earlier. For complicated data (like List-of-Numbers), look at the definition: There were two types of lists, so the function needs to ask which type it has:

   (if (empty? nums)
       ...
       ...)
   

4. Now we can even refine these ...s before we have to think: If we have an non-empty list, what are the (only) sub-parts we have to work with?

   (if (empty? nums)
       ...
       ...(first nums) ... (rest nums)...)
   

5. Finally, for any of these sub-parts which happen to be themselves valid inputs for the function we're writing, consider the natural recursive call (the one reflecting the definition's recursion):

   (if (empty? nums)
       ...
       ...(first nums) ... (our-function  (rest nums))...)
   

   Ask yourself what type of thing (first nums) and (our-function (rest nums)) are.
6. Okay, now the creative part: fill in the .... That is, if somebody gives you (first nums) and (our-function (rest nums)), how do you piece these two together to arrive at the desired answer for all of nums?
7. Finally, test your function by pressing execute and inspect the results. (If you cleverly put the examples from step 2 after your function, then you don't need to re-type or move anything around!)