ITEC 380 2013fall ibarland aaray

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

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).
        c. Add the natural recursive call (as appropriate)
        d. Inventory: In all cases, think about what type (each piece) is,
           and think of some functions that process that type.


  ---- Per function:
     4. write test cases
     5. (a-d): header, purpose, contract/type, 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
     8. run tests

1. Data def'n:

   A list-of-numbers is:
     - empty,
     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 ; (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.

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)

©2013, Ian Barland, Radford University Last modified 2013.Oct.07 (Mon)

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