Module 1 Abstractions (module 6)

Seeing strong similarities between programs or functions is not good: code that is copied between problems has risks:

it is a waste of time to re-write repeated code
it may contain errors

Process of abstraction

Implement
Extract differences as parameters
Re-design with abstraction

Example: string prefixing

; A ListOfStrings (LoS) is one of:
; - '()
; - (cons String LoS)
; Interpretation: a list of strings

(define LOS-0 '())
(define LOS-1 (cons "alice" LOS-0))
(define LOS-2 (cons "bob" LOS-1))

(define (los-temp los)
  (...
   (cond
     [(empty? los) ...]
     [(cons? los) ...
      (first los) ...
      (los-temp (rest los)) ...])))


;; prefix-strings : LOS String -> LOS
;; Prefix all items in the list of strings with String

(check-expect (prefix-strings LOS-0 "To: ") '())
(check-expect (prefix-strings LOS-1 "To: ") (list "To: alice"))
(check-expect (prefix-strings LOS-1 "From: ") (list "From: alice"))
(check-expect (prefix-strings LOS-2 "A ") (list "A bob" "A alice"))

(define (prefix-strings los s)
  (cond
    [(empty? los) '()]
    [(cons? los) (cons (string-append s (first los))
                       (prefix-strings (rest los) s))]))


; a) Design the function prefix-with-from, which accepts
; a ListOfStrings and prefixes every string with "From: "

;; prefix-with-from : LOS -> LOS
;; Prefixes strings with "From: "

(check-expect (prefix-with-from LOS-0) '())
(check-expect (prefix-with-from LOS-1) (list "From: alice"))
(check-expect (prefix-with-from LOS-2) (list "From: bob" "From: alice"))

(define (prefix-with-from los)
  (prefix-strings los "From: "))

; b) Design the function prefix-with-to, which accepts
; a ListOfStrings and prefixes every string with "To: "

;; prefix-with-to : LOS -> LOS
;; Prefixes strings with "To: "

(check-expect (prefix-with-to LOS-0) '())
(check-expect (prefix-with-to LOS-1) (list "To: alice"))
(check-expect (prefix-with-to LOS-2) (list "To: bob" "To: alice"))

(define (prefix-with-to los)
  (prefix-strings los "To: "))

First, create the prefix-string functions which is used in the two functions we create.

Abstracting data

Writing the same/similar data definitions for LOS and LON is wasteful and error-prone. The only difference is the data type.

The data type can be abstracted with

;; A [List-of X] is one of:
;; - '()
;; - (cons X [List-of X])
;; Interpretation: a list of elements of type X

Non-empty list

;; A [NEList-of X] is one of:
;; - (cons X '())
;; - (cons X [NEList-of X])

The smallest list that can be made is a list of one element (and the other element of the cons being the empty list).

(define NELON-1 (cons 3 '()))
(define NELON-2 (cons -4 NELON-1))

(define (nelon-template nelon)
  (cond
    [(empty? (rest nelon))
     (... (first nelon) ...)]
    [(cons? (rest nelon))
     (... (first nelon) ...
          (nelon-template (rest nelon)) ...)]))

Example: biggest number

Design the function biggest that returns the biggest number in a list of numbers, or #false if the list is empty.

First, design the data definition for Maybe, which we will use of [Maybe Number].

;; A [Maybe X] is one of:
;; - #false
;; - X

Design the biggest function:

;; biggest : [List-of Number] -> [Maybe Number]
;; Returns the biggest number, or #false is supplied an
;; empty list

(check-expect (biggest '()) #false)
(check-expect (biggest (cons 3 (cons -2 (cons 10 '())))) 10)

(define (biggest lon)
  (cond
    [(empty? lon) #false]
    [(cons? lon)
     (biggest/nelon lon)]))

In the cons? lon clause, although we have a lon-template that’s supposed to be there, we know that it is operating on a non-empty list. If the list was empty, it would have returned false, so that’s why we make a helper function for biggest/nelon lon.

;; biggest/nelon : [NEList-of Number] -> Number
;; Returns the largest number in a non empty list

(check-expect (biggest/nelon (cons 3 (cons -2 (cons 10 '())))) 10)

(define (biggest/nelon nelon)
  (cond
    [(empty? (rest nelon)) (first nelon)]
    [(cons? (rest nelon))
     (max (first nelon)
          (biggest/nelon (rest nelon)))]))

Abstracting a function with function data and parameterized signatures

Example: do to all

Performing a function on all values in a list and returning a new list

;; do-to-all : [List-of Number] [Number -> Number] -> [List-of Number]
;; Performs an operation on every element in a list

(check-expect (do-to-all LON-0 -) LON-0)
(check-expect (do-to-all LON-2 -) (cons -4 (cons -9 '())))

(define (do-to-all lon f)
   (cond
     [(empty? lon) '()]
     [(cons? lon)
      (cons (f (first lon))
       (do-to-all (rest lon) f))]))

Using this function, we can easily make other functions:

; sqrt-of-all : [List-of Number] -> [List-of Number]
; takes the square root of all input numbers

(check-expect
 (sqrt-of-all LON-0)
 LON-0)

(check-expect
 (sqrt-of-all LON-2)
 (cons 2 (cons 3 '())))

(define (sqrt-of-all lon)
  (do-to-all lon sqrt))

; sqr-of-all : [List-of Number] -> [List-of Number]
; squares all input numbers

(check-expect
 (sqr-of-all LON-0)
 LON-0)

(check-expect
 (sqr-of-all LON-2)
 (cons 16 (cons 81 '())))

(define (sqr-of-all lon)
  (do-to-all lon sqr))

Change the signature of do-to-all so it is not limited to numbers:

;; do-to-all : (X Y) [List-of X] [X -> Y] -> [List-of Y]
;; Performs an operation on every element in a list

Now it can work on strings, images, … too.

Keep if (filter)

;; keep-if : (X) [List-of X] [X -> Boolean] -> [List-of X]
;; Keeps a part of the list based on the predicate

(check-expect (keep-if (cons 1 (cons 2 (cons 3 '()))) odd?)
              (cons 1 (cons 3 '())))


(define (keep-if lox pred?)
  (cond
    [(empty? lox) lox]
    [(cons? lox)
     (if (pred? (first **lox**))
         (cons (first lox)
               (keep-if (rest lox) pred?))
         (keep-if (rest lox) pred?))]))

Collapse

Designing a Useful List Abstraction (collapse, Part 1)

; A [List-of Number] is one of
; - '()
; - (cons Number [List-of Number])
; Interpretation: ...
 
(define LON-0 '())
(define LON-1 (cons 2 LON-0))
(define LON-2 (cons 3 LON-1))
(define LON-3 (cons 4 LON-2))

;; collapse : (X Y) [List-of X] Y [X Y -> Y] -> Y
;; Collapse a list into a value, f being the combiner function
;; Second value of [X Y -> Y] is the base value (base) 

(check-expect
 (collapse (list "a" "b" "c") "" string-append)
 "abc")

(check-expect (collapse LON-3 '() cons) LON-3)

(check-expect (collapse LON-3 0 +) 9)
(check-expect (collapse LON-3 1 *) 24)


(define (collapse lox base f)
  (cond
    [(empty? lox) base]
    [(cons? lox) (f (first lox)
                    (collapse (rest lox) base f))]))