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:

• What is the function going to produce? What does the function consume?
  • This narrows down which functions you need to consider; you can filter many of them out based on their contracts alone.
• Assuming that the desired function has the contract [Listof A] -> [Listof B], (for some A and B),
  • Is the length of the output list sometimes smaller than the length of the input list, and never larger? In that case, consider using filter.
  • Is A a different class of data from B? In that case, consider using map.
• Do you need to construct a list, but you don't get one as input? In that case, consider using build-list.
• Do you need to produce a boolean? In that case, consider using andmap or ormap, depending on whether you're asking if a predicate holds for every item in the list, or only if there exists some item for which it holds.

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]

map : (Symbol -> String) [Listof Symbol] -> [Listof String]

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")