Lab 10: The wishlist method

8.16

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 a sorting function. In Lecture 20: Insertion sort Exercise 1, you did steps 1–4 of the design recipe:

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

Hence, the template provides the two ingredients 70 and EXPECTED-RECURSIVE-RESULT. They are what’s in the fridge.

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 (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 the definition of insert-sort by changing the dots in the template to the name of the HELPER function.

Exercise 5. All you have left to do is to design the helper. You did this in Lecture 20: Insertion sort Exercise 2. Follow the design recipe:

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.
Write the usual template for processing the input list.
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.
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.
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 6. 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 7. 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 6. So, the very end of your calculation should look like this:

= (... "Indiana"
EXPECTED-RECURSIVE-RESULT)

Hence, the template provides the two ingredients "Indiana" and EXPECTED-RECURSIVE-RESULT. They are what’s in the fridge.

Exercise 8. 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 (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 9. Finish the definition of prefixes by changing the dots in the template to the name of the HELPER function.

Exercise 10. All you have left to do is to design the helper. Follow the design recipe:

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.
Write the usual template for processing the input list.
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.
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.
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 11. 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 12. 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 11. So, the very end of your calculation should look like this:

= (... "spinach"
EXPECTED-RECURSIVE-RESULT)

Hence, the template provides the two ingredients "spinach" and EXPECTED-RECURSIVE-RESULT. They are what’s in the fridge.

Exercise 13. 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 (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 14. Finish the definition of sublists by changing the dots in the template to the name of the HELPER function.

Exercise 15. All you have left to do is to design the helper. Follow the design recipe:

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.
Write the usual template for processing the input list.
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.
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.
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 16. 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 17. 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 16. So, the very end of your calculation should look like this:

= (... (list "soup" "salad" "fries")
EXPECTED-RECURSIVE-RESULT)

Hence, the template provides the two ingredients (list "soup" "salad" "fries") and EXPECTED-RECURSIVE-RESULT. They are what’s in the fridge.

Exercise 18. 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 (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 19. Finish the definition of deals by changing the dots in the template to the name of the HELPER function.

Exercise 20. All you have left to do is to design the helper. Follow the design recipe:

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.

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 (HELPER course meals)
  (cond [(empty? course) ...]
        [else (... (first course)
                   meals
                   (HELPER (rest course) meals))]))

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.
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.
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 HELPER and use it to redo this exercise.
Finish the definition of HELPER by changing the dots in the template to the name of the latest helper function.
All you have left to do is to design the latest helper. Follow the design recipe. Process the second of the three inputs.

5 Challenge: Permutations🔗

Exercise 21. Design this function using the wishlist method.

; permutations : [ListOf X] -> [ListOf [ListOf X]]
; all the permutations of the given list
(check-expect (permutations empty)
              (list empty))
(check-expect (permutations (list 3))
              (list (list 3)))
(check-expect (permutations (list 2 3))
              (list (list 2 3) (list 3 2)))
(check-expect (permutations (list 1 2 3))
              (list (list 1 2 3) (list 2 1 3) (list 2 3 1)
                    (list 1 3 2) (list 3 1 2) (list 3 2 1)))

Design the helper using the wishlist method.

contents ← prev up next →

	Syllabus
	Tutoring
	Software
	Lectures
	Readings
	Labs
	Problem sets
	Extra credit
	Due dates

	Lab 1: Getting started
	Lab 2: The design recipe
	Lab 3: Multiple cases
	Lab 4: Structures
	Lab 5: Unions
	Lab 6: Recursive unions
	Lab 7: Secret messages
	Lab 8: Blending curves
	Lab 9: Built-in abstractions
	Lab 10: The wishlist method
	Lab 11: Forking turtles
	Lab 12: Generative recursion
	Lab 13: Accumulators
	Lab 14: Bus mapping
	Lab 15: Final exam prep