Lab 9. Loops

When designing a function, often one can use a pre-existing "abstract list function" (or loop) to do the bulk of the work. (You can find the specification for the important loops on page 313.)


1.1 Loop questions

But one must know how to select the proper loop for the job. You need to ask yourself questions about the problem:

Note that you may need to combine more than one loop together to get the desired effect.


1.2 Loop contracts

Once you have selected a loop function, you need to determine how to invoke it; that is, you need to figure out what kind of function you need to pass into the loop. The key to this step is to figure out what X and Y are in the contract for the loop. You can determine this based on the classes of data the loop is consuming and producing.


1.3 Example loop selection

For example, if we know that we want a [Listof String] as output, and we have a [Listof Symbol] as input, then we can consult page 313 and determine:

  1. build-list has potential, because it produces a [Listof X]. But it takes a number as input, not a list. So that's not it.
  2. filter takes a list as input and produces a list as output; much better!
    On closer inspection, the contract for filter is:
    filter : (X -> Boolean) [Listof X] -> [Listof X]
    So to get a [Listof String] out, we need to let X be String.
    But then that means that filter needs a [Listof String] as input, and all we have is a [Listof Symbol]. So that's not it.
  3. quicksort has the same problem as filter; it only produces [Listof String] when it is given a [Listof String]. So that's not it.
  4. map takes a [Listof X] and produces a [Listof Y]. This means that we can let Y be String, and we're still free to choose some other X to suit our needs; excellent!

We need to read the purpose statement for map to tell if it really is the right fit for our needs. For example, if we wanted the output list to be double the length of the input list, then map alone isn't going to be sufficient. Let us assume that map's specification suits the needs of our problem.

Now the only thing left is to determine what we need to feed to map for it to do its job. The contract for map is:

map : (X -> Y) [Listof X] -> [Listof Y]
So when we let X be Symbol and Y be String, we find that map satisfies the contract:
map : (Symbol -> String) [Listof Symbol] -> [Listof String]
We've already got the [Listof Symbol] ready; so all we need to do is find (or design) a function that turns Symbols into Strings in the manner that we desire.


1.4 Loop exercises

Exercise 1: Determine what class of data each of the following expressions belongs to (assuming the contracts given in the comments are correct).

;; A Nat is a natural number (0, 1, 2, ...)

;; f : Nat -> String
(build-list 10 f) ;; : ???

;; g : Nat -> Boolean
(map g (list 1 2 3 4)) ;; : ???

;; h : Nat -> [Listof Symbol] 
(build-list 20 h) ;; : ???

;; i : String -> Boolean
(andmap i (list "hello" "world")) ;; : ???

;; j : String -> Boolean
(filter j (list "goodbye" "cruel" "world")) ;; : ???

;; k : (Number String -> String)
(foldr k "what me worry?" (list 1 2)) ;; : ???


Exercise 2: Determine what class of data each of question-marked contracts (i.e. the bits labelled ???) must describe in order for the associated loop expression to belong to the class of data ascribed to it.

;; z : ???
(quicksort (list 1 2 3) z) ;; : [Listof Number]

;; y : ???
;; x : Number -> String
(filter y (map x (list 10 9 8 7))) ;; : [Listof String]

;; w : ???
;; v : Symbol -> Number
(map w (build-list (v 'x) add1)) ;; : [Listof Symbol]

;; t : ???
;; s : ???
(ormap t (filter s (list "it's" "me" "mom"))) ;; : Boolean


Exercise 3: (recall recall) Using an appropriate loop, design the function recall to eliminate specific toys from a list. The function consumes the name of a toy, called ty, and a list of names, called lon, and produces a list of names that contains all components of lon with the exception of ty. For example,

(recall 'robot (cons 'robot (cons 'doll (cons 'dress empty))))
;; expected value: 
(cons 'doll (cons 'dress empty))


Exercise 4: (a substitute for substitute) Using an appropriate loop, design the function substitute. The new function consumes two symbols, called new and old, and a list of symbols. It produces a new list of symbols by substituting all occurrences of old by new. For example,

(substitute 'Barbie 'doll (cons 'robot (cons 'doll (cons 'dress empty))))
;; expected value: 
(cons 'robot (cons 'Barbie (cons 'dress empty)))

Exercise 5: (summarizing our knowledge with sum-num) Using an appropriate loop, design the function sum-num which takes a [Listof Number] and produces the sum of all the numbers in the list. For example,

(equal? (sum-num (list 1 2 3 4)) 10)


Exercise 6: (sum-str with knowledge our summarizing) Using an appropriate loop, design the function sum-str which takes a [Listof String] and produces a single string that is the result of appending all of the strings together in reverse order. For example,

(equal? (sum-str (list "Harry" "Potter" "Ice Cream")) "Ice CreamPotterHarry")