Using Templates Effectively

Many of you headed down complicated paths when asked to implement sort following the template today. Most of you ran into one of two (related) problems:

• You started thinking about algorithms too early
• You weren't sure how to use the template

Templates defer questions about the logic/algorithm of a program until after its core structure is in place. If you know how to use the template, you get a lot of code written down that can then help you think out an algorithm. The design process becomes a lot more manageable.

Step 1: Write the Template

Writing the template means writing the whole template, not just the cond (because as soon as you had that much you started thinking about the algorithm). The whole template for sort looked like

;; sort : list-of-number -> list-of-number[sorted]
;; sort list of numbers into increasing order
(define (sort alon)
  (cond [(empty? alon) ...]
        [(cons? alon)
         ... (first alon) 
         ... (sort (rest alon))]))

If you gave any thought to the sort algorithm before you had this much on paper, you started thinking about the algorithm too early.

Step 2: Use the template to suggest an algorithm

Filling in the empty case was easy -- that came from the examples. What do you do in the cons case? Again, many of you started thinking about the algorithm, instead of thinking about what the template gave you for free. To use the template, ask yourself the following questions:

1. What does (first alon) give me? [Answer: a number]
2. What does (sort (rest alon)) give me? [Answer: the rest of the list sorted -- read this right off the purpose statement!!]
3. How do I combine a number and a sorted list of numbers into a sorted list of numbers? [Here's the algorithm part!]

Answering the third question leads you to an algorithm: stick (or insert) the number into its appropriate place in a list of numbers. How do you do that? That sounds like a straightforward program on list of numbers (it is, and one you should certainly be able to write). Modify the template with a helper function name for this new algorithm you need, then write the insert helper function to finish sort.

;; sort : list-of-number -> list-of-number[sorted]
;; sort list of numbers into increasing order
(define (sort alon)
  (cond [(empty? alon) empty]
        [(cons? alon)
         (insert (first alon) 
		 (sort (rest alon)))]))

Moral: Learn To Ask Yourself Template Questions!

Learning to ask yourself the template questions above (what does each piece give me and how do I combine them--use the contract and purpose to help) will dramatically improve your skills at working with templates. Internalize these questions.

But Wait ...

Doesn't this suggest that you can never write a different sorting algorithm besides insertion sort? Tune in next time ...