►C211/  H211:   Introduction to Computer Science
▼Labs
►Lab 10:   The wishlist method
On this page:
2 Prefixes
3 Sublists
4 Deals
8.14
    contents    up   

Lab 10: The wishlist method🔗

Congratulations! You finished the second midterm! You learned how to design a function!

The class is going to get harder now, because we are going to turn from designing a single function to designing larger programs where multiple functions help each other. We will teach you a suite of techniques for designing those larger programs, but you will need to master the thought process of the design recipe, now more than ever.

The problems in this lab might look difficult, but they are actually easy to solve as long as you stick to the thought process of the design recipe. As you weave together your examples and template, the design recipe even tells you what helper function you need.

1 Sort🔗

The goal of this section is to design this function:
; insert-sort : [ListOf Number] -> [ListOf Number]
; sort numbers into ascending order
(check-expect (insert-sort (list 70 10 60 90 20))
              (list 10 20 60 70 90))
(define (insert-sort lst)
  (cond [(empty? lst) ...]
        [else (... (first lst) (insert-sort (rest lst)))]))

Exercise 1. In the template provided above, point out where insert-sort calls itself. Then, list all the recursive calls made by the test provided above. Write each of these calls as additional tests, to form a sequence of tests.

Exercise 2. Calculate step-by-step, using just the template provided above:
  (insert-sort (list 70 10 60 90 20))
= ???
But when you get to the recursive call, step directly to what the result of the call should be. You wrote down this result in Exercise 1. So, the very end of your calculation should look like this:
= (... 70
       EXPECTED-RECURSIVE-RESULT)

Exercise 3. Don’t you wish you could fill in the template just by changing the dots to the name of a function? In your calculation, change the dots to the name of a new helper function (which doesn’t exist yet—make up a new name). Based on the very end of your calculation, write a test for this new helper:
(check-expect (NEW-HELPER 70
                          EXPECTED-RECURSIVE-RESULT)
              EXPECTED-OVERALL-RESULT)

Examine this test to figure out the signature, purpose, and header of this new helper. If you are unsure, write a fresh new test for insert-sort and use it to redo the exercises so far.

Exercise 4. Finish designing the helper. Follow the design recipe:

  1. The wishlist method above helped you hit the ground running: Check that you already have the necessary data definition, signature, purpose, header, and at least one example.

  2. Write the usual template for processing the input list.

  3. In your template, point out the recursive call. Then, list all the recursive calls made by the test(s) you wrote. Write each of these calls as additional tests.

  4. Pick a test of moderate size, and calculate step-by-step, using just the template you wrote. But when you get to the recursive call, step directly to what the result of the call should be, which you just wrote down.

  5. What ingredients does the template provide? How do you turn these ingredients into the expected result?

2 Prefixes🔗

A prefix of a list is made of the first few elements of the list. For example, the list
(list "Indiana" "Dunn" "Grant")
is a prefix of the list
(list "Indiana" "Dunn" "Grant" "Lincoln" "Washington" "Walnut" "College")
Actually, the prefix can have any number of elements: On one hand, the empty (list) is a prefix of any list. On the other hand, every list is a prefix of itself.

The goal of this section is to design this function:
; prefixes : [ListOf X] -> [ListOf [ListOf X]]
; all the prefixes of the given list, from long to short
(check-expect (prefixes (list "Indiana" "Dunn" "Grant" "Lincoln"))
              (list (list "Indiana" "Dunn" "Grant" "Lincoln")
                    (list "Indiana" "Dunn" "Grant")
                    (list "Indiana" "Dunn")
                    (list "Indiana")
                    (list)))
(define (prefixes lst)
  (cond [(empty? lst) ...]
        [else (... (first lst) (prefixes (rest lst)))]))

Exercise 5. In the template provided above, point out where prefixes calls itself. Then, list all the recursive calls made by the test provided above. Write each of these calls as additional tests, to form a sequence of tests.

Exercise 6. Calculate step-by-step, using just the template provided above:
  (prefixes (list "Indiana" "Dunn" "Grant" "Lincoln"))
= ???
But when you get to the recursive call, step directly to what the result of the call should be. You wrote down this result in Exercise 5. So, the very end of your calculation should look like this:
= (... "Indiana"
       EXPECTED-RECURSIVE-RESULT)

Exercise 7. Don’t you wish you could fill in the template just by changing the dots to the name of a function? In your calculation, change the dots to the name of a new helper function (which doesn’t exist yet—make up a new name). Based on the very end of your calculation, write a test for this new helper:
(check-expect (NEW-HELPER "Indiana"
                          EXPECTED-RECURSIVE-RESULT)
              EXPECTED-OVERALL-RESULT)

Examine this test to figure out the signature, purpose, and header of this new helper. If you are unsure, write a fresh new test for prefixes and use it to redo the exercises so far in this section.

Exercise 8. Finish designing the helper. Follow the design recipe:

  1. The wishlist method above helped you hit the ground running: Check that you already have the necessary data definition, signature, purpose, header, and at least one example.

  2. Write the usual template for processing the input list.

  3. In your template, point out the recursive call. Then, list all the recursive calls made by the test(s) you wrote. Write each of these calls as additional tests.

  4. Pick a test of moderate size, and calculate step-by-step, using just the template you wrote. But when you get to the recursive call, step directly to what the result of the call should be, which you just wrote down.

  5. What ingredients does the template provide? How do you turn these ingredients into the expected result?

3 Sublists🔗

A sublist of a list is made of some elements of the list. For example, the list
(list "pineapple" "sausage")
is a sublist of the list
(list "spinach" "pineapple" "feta" "sausage")
As long as the elements stay in the same order, the sublist can have any number of elements: On one hand, the empty (list) is a sublist of any list. On the other hand, every list is a sublist of itself.

The goal of this section is to design this function:
; sublists : [ListOf X] -> [ListOf [ListOf X]]
; all the sublists of the given list, alternating between excluding
; the first given element and including the first given element
(check-expect (sublists (list "spinach" "pineapple" "feta" "sausage"))
              (list (list)
                    (list "spinach")
                    (list "pineapple")
                    (list "spinach" "pineapple")
                    (list "feta")
                    (list "spinach" "feta")
                    (list "pineapple" "feta")
                    (list "spinach" "pineapple" "feta")
                    (list "sausage")
                    (list "spinach" "sausage")
                    (list "pineapple" "sausage")
                    (list "spinach" "pineapple" "sausage")
                    (list "feta" "sausage")
                    (list "spinach" "feta" "sausage")
                    (list "pineapple" "feta" "sausage")
                    (list "spinach" "pineapple" "feta" "sausage")))
(check-expect (sublists (list "pineapple" "feta" "sausage"))
              (list (list)
                    (list "pineapple")
                    (list "feta")
                    (list "pineapple" "feta")
                    (list "sausage")
                    (list "pineapple" "sausage")
                    (list "feta" "sausage")
                    (list "pineapple" "feta" "sausage")))
(check-expect (sublists (list))
              (list (list)))
(define (sublists lst)
  (cond [(empty? lst) ...]
        [else (... (first lst) (sublists (rest lst)))]))

Exercise 9. In the template provided above, point out where sublists calls itself. Then, list all the recursive calls made by the test provided above. Write each of these calls as additional tests, to form a sequence of tests.

Exercise 10. Calculate step-by-step, using just the template provided above:
  (sublists (list "spinach" "pineapple" "feta" "sausage"))
= ???
But when you get to the recursive call, step directly to what the result of the call should be. You wrote down this result in Exercise 9. So, the very end of your calculation should look like this:
= (... "spinach"
       EXPECTED-RECURSIVE-RESULT)

Exercise 11. Don’t you wish you could fill in the template just by changing the dots to the name of a function? In your calculation, change the dots to the name of a new helper function (which doesn’t exist yet—make up a new name). Based on the very end of your calculation, write a test for this new helper:
(check-expect (NEW-HELPER "spinach"
                          EXPECTED-RECURSIVE-RESULT)
              EXPECTED-OVERALL-RESULT)

Examine this test to figure out the signature, purpose, and header of this new helper. If you are unsure, write a fresh new test for sublists and use it to redo the exercises so far in this section.

Exercise 12. Finish designing the helper. Follow the design recipe:

  1. The wishlist method above helped you hit the ground running: Check that you already have the necessary data definition, signature, purpose, header, and at least one example.

  2. Write the usual template for processing the input list.

  3. In your template, point out the recursive call. Then, list all the recursive calls made by the test(s) you wrote. Write each of these calls as additional tests.

  4. Pick a test of moderate size, and calculate step-by-step, using just the template you wrote. But when you get to the recursive call, step directly to what the result of the call should be, which you just wrote down.

  5. What ingredients does the template provide? How do you turn these ingredients into the expected result?

4 Deals🔗

Some restaurants offer meal deals like this: the customer can choose one appetizer out of a list of appetizers, one main entrée out of a list of main entrées, and one dessert out of a list of desserts. That would make a 3-course meal, but some restaurants offer 2-course meals or 5-course meals.

The goal of this section is to design this function:
; A Course is a [ListOf String]
; A Meal is a [ListOf String]
 
; deals : [ListOf Course] -> [ListOf Meal]
; all the meals that choose one option from each course,
; grouped by choice of first course
(check-expect (deals (list (list "soup" "salad" "fries")
                           (list "sandwich" "stir fry")
                           (list "chocolate" "tofu" "affogato")))
              (list (list "soup" "sandwich" "chocolate")
                    (list "soup" "sandwich" "tofu")
                    (list "soup" "sandwich" "affogato")
                    (list "soup" "stir fry" "chocolate")
                    (list "soup" "stir fry" "tofu")
                    (list "soup" "stir fry" "affogato")
                    (list "salad" "sandwich" "chocolate")
                    (list "salad" "sandwich" "tofu")
                    (list "salad" "sandwich" "affogato")
                    (list "salad" "stir fry" "chocolate")
                    (list "salad" "stir fry" "tofu")
                    (list "salad" "stir fry" "affogato")
                    (list "fries" "sandwich" "chocolate")
                    (list "fries" "sandwich" "tofu")
                    (list "fries" "sandwich" "affogato")
                    (list "fries" "stir fry" "chocolate")
                    (list "fries" "stir fry" "tofu")
                    (list "fries" "stir fry" "affogato")))
(check-expect (deals (list))
              (list (list)))
(define (deals lst)
  (cond [(empty? lst) ...]
        [else (... (first lst) (deals (rest lst)))]))

Exercise 13. In the template provided above, point out where deals calls itself. Then, list all the recursive calls made by the test provided above. Write each of these calls as additional tests, to form a sequence of tests.

Exercise 14. Calculate step-by-step, using just the template provided above:
  (deals (list (list "soup" "salad" "fries")
               (list "sandwich" "stir fry")
               (list "chocolate" "tofu" "affogato")))
= ???
But when you get to the recursive call, step directly to what the result of the call should be. You wrote down this result in Exercise 13. So, the very end of your calculation should look like this:
= (... (list "soup" "salad" "fries")
       EXPECTED-RECURSIVE-RESULT)

Exercise 15. Don’t you wish you could fill in the template just by changing the dots to the name of a function? In your calculation, change the dots to the name of a new helper function (which doesn’t exist yet—make up a new name). Based on the very end of your calculation, write a test for this new helper:
(check-expect (NEW-HELPER (list "soup" "salad" "fries")
                          EXPECTED-RECURSIVE-RESULT)
              EXPECTED-OVERALL-RESULT)

Examine this test to figure out the signature, purpose, and header of this new helper. If you are unsure, write a fresh new test for deals and use it to redo the exercises so far in this section.

Exercise 16. Finish designing the helper. Follow the design recipe:

  1. The wishlist method above helped you hit the ground running: Check that you already have the necessary data definition, signature, purpose, header, and at least one example.

  2. Write the template for processing the first input list:

    We choose to process the first input list rather than the second input list, because the purpose of deals says “grouped by choice of first course”.

    (define (NEW-HELPER course meals)
      (cond [(empty? course) ...]
            [else (... (first course)
                       meals
                       (NEW-HELPER (rest course) meals))]))

  3. In your template, point out the recursive call. Then, list all the recursive calls made by the test(s) you wrote. Write each of these calls as additional tests.

  4. Pick a test of moderate size, and calculate step-by-step, using just the template you wrote. But when you get to the recursive call, step directly to what the result of the call should be, which you just wrote down.

  5. Don’t you wish you could fill in the template just by changing the dots to the name of a function? In your calculation, change the dots to the name of a new helper function (which doesn’t exist yet—make up a new name). Based on the very end of your calculation, write a test for this new helper.

    Examine this test to figure out the signature, purpose, and header of this new helper. If you are unsure, write a fresh new test for NEW-HELPER and use it to redo this exercise.

  6. Finish designing the helper. Follow the design recipe. Process the second of the three inputs.

    contents    up