ITEC 380 2016fall ibarland

home—lectures—recipe—exams—hws—D2L—breeze (snow day; distance)

the-design-recipe
the design recipe
final version

  ---- Per data type:
     1. Choose data definition
     2. Give some examples of the data
     3. Template:
        a. If handling a union type, include a cond w/ one branch per option.
        b. If handling a product-type, pull out each piece (field).
           (Do this for an overall product-type, or within cond-branches from (a).)
        c. Inventory: In all cases, think about what type (each piece) is,
           and think of some functions that process that type.
        d. Add the natural recursive call (as appropriate).


  ---- Per function:
     4. write test cases
     5. (a-d): contract/type, purpose, header, copy the template and stub it.
     6. Inventory with values: Consider a particular test case,
        and think about what specific value of each sub-expression.
     7. complete the body-expression
     8. run tests

1. Data def'n: A list-of-numbers is:
   • '(), OR
   • (cons [number] [list-of-numbers])
2. Examples of the data

   empty (cons 4 empty) (cons 2 (cons 4 empty)) (cons 93 (cons 2 (cons 4 empty)))

3. Template for any function that handles a list-of-numbers:

   ; func-for-nums : list-of-numbers -> ??? ; (define (func-for-nums a-lon) (cond [(empty? a-lon) ...] [(cons? a-lon) (...(first a-lon) ... (func-for-nums (rest a-lon)))]))

   Remember to think of the type of each of these items: When we're in the second branch (a-lon is a cons?), (first a-lon) is a number (we can use functions like +, >, etc.); (rest a-lon) is a list-of-numbers (we can use functions like ... well I guess func-for-list-of-numbers). At this point, we don't know the type that that (func-for-list-of-numbers (rest a-lon)) evaluates to, because we don't know what type the function will be returning.

---

For a specific problem, e.g. contains?:
4. Write the test cases

   (check-expect (contains? empty 4) false) (check-expect (contains? (cons 4 empty) 4) true) (check-expect (contains? (cons 4 empty) 99) false) (check-expect (contains? (cons 2 (cons 4 empty)) 99) false) (check-expect (contains? (cons 2 (cons 4 empty)) 2) true) (check-expect (contains? (cons 2 (cons 4 empty)) 4) true) (check-expect (contains? (cons 93 (cons 2 (cons 4 empty))) 93) true) (check-expect (contains? (cons 93 (cons 2 (cons 4 empty))) 4) true) (check-expect (contains? (cons 93 (cons 2 (cons 4 empty))) 77) false) (check-expect (contains? (cons 93 (cons 2 (cons 93 empty))) 93) true)

5. header, purpose, contract/type, copy the template, and stub it.

   ; contains? : list-of-number, number -> boolean ; Does `target` occur inside `a-lon`? ; (define (contains? a-lon target) (cond [(empty? a-lon) ...] [(cons? a-lon) (...(first a-lon) ... (contains? (rest a-lon) target))]))

6. Inventory with values: Consider a particular test case, and think about what specific value of each sub-expression.
   • Suppose a-lon is the list (cons 93 (cons 2 (cons 4 empty)))
   • Then (first a-lon) is ...93.
   • Then (rest a-lon) is ...(cons 2 (cons 4 empty)).
   • Then (contains? (rest a-lon) target) is ... true.

7. Only now do you complete the template.

   In this example: You are given 93 and true (and target=4), and this is where your thinking begins.
   What is the rule we want, so that we achieve our test cases:

   • when we have 93 and true (and target=4) our result should be true (by our test-case),
   • and when we have 93 and false (and target=4) our result should be false (by a different test-case),
   • and when we have 4 and false (and target=4) our result should be true?
   Note that our thinking does not involve lists at all! — the template has already done the list-processing, and the only code that varies from writing one function or another is how to assemble the results of calling the recursive function.

   (If you have code that is missing a recursive call, it means you skipped part of step 5 above.)

8. Run your tests.

If getting stuck

First, make sure that you do each step, in order. Each step plays helps nudge you to get correct answers to later steps!

Example: When you're pulling out fields of a struct and asking what type they are, you are relying on the data-definition, which included exactly that info.
When you're looking at the result of the recursive call and how to use it, you use the return-type listed in your function-header
In general, every step is used in at least one following step.

Help with the inventory-with-values:
For example, if working with a list template, the “inventory with values” means writing down the following:

Let's do an inventory-with-values: 
pick a particular value for `a-lon`, and see what the two pieces from the template refer to, in that case.
So, reply back w/ filling out this table:

(a) My sample particular value to use for `a-lon`:  ________________________________________
(b) what is `(first a-lon)` in this case: __________
(c) what is `(map-sqr (rest a-lon))` in this case:   ________  (Note: I'm *not* asking for `(rest a-lon)`, but the result of giving `(rest a-lon)` to `map-sqr`.)
(d) What is the value that I would want the overall function to return, in this case? _________________________________

(e) How did I combine (b) and (c) to get (d)?
(f) How, in the *general* case, will I combine `(first a-lon)` with `(map-sqr (rest a-lon))` to get my desired answer?

More examples of following the design recipe are in lect09-structs1.rkt (unions and structs) in lect11-structs2.rkt (structs containing structs, structs containing unions, ...) and in lect14-list-intro.rkt (incl. recursively-defined lists).

home—lectures—recipe—exams—hws—D2L—breeze (snow day; distance)

©2016, Ian Barland, Radford University Last modified 2016.Sep.12 (Mon)

Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu