5 Wednesday Morning: Creating Abstractions

Related material in How to Design Programs: part iv

5.1 Goal

to abstract over recurring patterns in functions, why it matters

the design recipe

recognize patterns in two functions: circle the differences and connect them with lines in the two definitions;
for each pair of differences, introduce a new parameter and use it in place of the circled deltas;
define each of the old functions in terms of the abstraction and use the old test suite to ensure that things still work.

5.2 Example: Functions are Values, too

What’s the difference?

;; draw-ufo : Posn  →  true
;; draw a red disk at p
(define (draw-ufo p) 
  (fboxdraw-solid-disk p 3 'red))

;; clear-ufo : Posn  →  true
;; erase a red disk at p
(define (clear-ufo p)
  (fboxclear-solid-disk p 3 'red))

Doing better:¹

;; dc-ufo : Posn ???  →  true
;; draw or erase a red disk at p
(define (clear-ufo p action)
  (action p 3 'red))

;; draw-ufo : Posn  →  true
;; draw a red disk at p
(define (draw-ufo p) 
  (dc-ufo p draw-solid-disk))

;; clear-ufo : Posn  →  true
;; erase a red disk at p
(define (clear-ufo p) 
  (dc-ufo p clear-solid-disk))

Now change the shape of the UFOs.

5.3 Example: Primitives are Values, too

;; NumberList  →  NumberList
;; extract all items from l 
;; that are smaller than pivot
(define (smaller pivot l)
  (cond
    [(empty? l) empty]
    [else
      (cond
	[(fbox< (first l) pivot)
	 (cons (first l)
	   (smaller pivot (rest l)))]
	[else
	  (smaller pivot (rest l))])]))

;; test:
(equal? (smaller 3 (list 1 2 3 4 5))
        (list 1 2))

;; NumberList  →  NumberList
;; extract all items from l 
;; that are larger than pivot
(define (larger pivot l)
  (cond
    [(empty? l) empty]
    [else
      (cond
	[(fbox> (first l) pivot)
	 (cons (first l)
	   (larger pivot (rest l)))]
	[else
	  (larger pivot (rest l))])]))

;; test:
(equal? (larger 3 (list 1 2 3 4 5))
        (list 4 5))

;; NumberList ???  →  NumberList
;; extract all items from l 
;; that are cmp to pivot
(define (extract pivot l cmp)
  (cond
    [(empty? l) empty]
    [else (cond
	    [(fboxcmp (first l) pivot)
	     (cons (first l) (extract pivot (rest l)))]
	    [else (extract pivot (rest l))])]))

(define (smaller pivot l)
  (extract pivot l <))

;; test:
(equal? (smaller 3 (list 1 2 3 4 5))
        (list 1 2))

(define (larger pivot l)
  (extract pivot l >))

;; test:
(equal? (larger 3 (list 1 2 3 4 5))
        (list 4 5))

Now extract all those numbers equal to pivot. Why?

5.4 Example: More on Functions

;; PosnList  →  NumberList 
;; extract the  x coordinates
;; from the Posns
(define (xxxs pl)
  (cond
    [(empty? pl) empty]
    [else
      (cons
	(posn-x (first pl))
	(xxxs (rest pl)))]))

;; Test:
(equal? 
 (xxxs
  (list
    (make-posn 3 4)
    (make-posn 12 5)
    (make-posn 17 20)
    (make-posn 22 1)))
 (list
   3
   12
   12
   22))

;; ColorList  →  ColorList
;; remove green from every color on cl
;; see section 1.5
(define (remove-all-green cl)
  (cond
    [(empty? cl) empty]
    [else
      (cons
	(remove-green (first cl))
	(remove-all-green (rest cl)))]))

;; Test:
(equal? (remove-all-green
	  (cons
	    (make-color 100 100 100) 
	    (cons
	      (make-color 200 100 0)
	      empty)))
        (cons
	  (make-color 100 0 100) 
	  (cons
	    (make-color 200 0 0)
	    empty)))

;; ???List ???  →  ???List
;; use f on every item in l
(define (every l f)
  (cond
    [(empty? l) empty]
    [else (cons (f (first l)) (every (rest l) f))]))

(define (xxxs gl)
  (every gl one-gpa))

(define (remove-all-green cl)
  (every cl remove-green))

Now extract all x-coordinates from a list of Posns.

5.5 Example: Contracts are People, too

A list-of-GradeRs is either

empty
(cons n l)
where n is a GradeR
and n is a list-of-GradeRs.
A list-of-Colors is either

empty
(cons n l)
where n is a Color
and n is a list-of-Colors.

Use (Listof X) instead.

5.6 Function have Contracts, too

We have:

;; tax: Number  →  Number

;; xxxs: PosnList  →  NumberList

;; draw-ufo : Posn  →  true

So it’s not surprising that:

;; draw-solid-disk : Posn Number ColorSymbol  →  true

;; < : Number Number  →  Boolean

;; remove-green : Color  →  Color

;; one-gpa : GradeR  →  GPA

And therefore:

;; dc-ufo : Posn (Posn Number ColorSymbol  →  true)  →  true

;; extract : NumberList (Number Number  →  Boolean)  →  NumberList

But what about every? (Listof X) (X → Y) → (Listof Y)

¹ There is a different alternative.