Hailperin, Chapter 7

Slide, The definition of a list

Demo car, cdr, cons, null? with and without quote and with nested lists

> (cons 'a (cons 'b (cons 'c ())))

list is a shortcut.

> (list 'a 'b 'c)

Demo integers-from-to in ch7a.rkt

> (integers-from-to 3 7)
> (integers-from-to 3 2)

Write integers-from-to, reveal line by line in ch7a.rkt

(define integers-from-to
  (lambda (low high)
    (if (> low high)
        '()
        (cons low  
              (integers-from-to (+ 1 low) high)))))

Demo my-length

> (my-length '(a b c))
> (my-length ())

Write my-length

(define my-length
  (lambda (lst)
    (if (null? lst)
        0
        (+ 1 (my-length (cdr lst))))))

Demo sum

> (sum '(3 7 2))
> (sum ())

Write sum

(define sum
  (lambda (lst)
    (if (null? lst)
        0
        (+ (car lst) (sum (cdr lst))))))

Demo my-filter

> (my-filter odd? '(2 5 9 6 12 1))

Write my-filter

;; Returns a list of the elements in lst that
;; satify the predicate ok?.
(define my-filter
  (lambda (ok? lst)
    (cond ((null? lst)
           '())
          ((ok? (car lst))
           (cons (car lst) (my-filter ok? (cdr lst))))
          (else
           (my-filter ok? (cdr lst))))))

Demo first-elements-of

> (first-elements-of 3 '(a b c d e f g))
> (first-elements-of 3 '(a b))  ; Does not work

Write first-elements-of

;; Returns a list of the first n elements of lst.
(define first-elements-of
  (lambda (n lst)
    (if (= n 0)
        '()
        (cons (car lst) 
              (first-elements-of (- n 1)
                                 (cdr lst))))))

Demo interleave, show the first two lines with the specification

> (interleave '(a b c) '(d e f))
> (interleave '(a b c d e f) '(g h i))
> (interleave '(a b c) '(d e f g h i))

interleave slides
=================

Write interleave

(define interleave    ; interleaves lst1 and lst2, starting with
  (lambda (lst1 lst2) ; the first element of lst1 (if any)
    (if (null? lst1)
        lst2
        (cons (car lst1)
              (interleave lst2 (cdr lst1))))))

Demo built-in list-tail function

> (list-tail '(a b c d e f g h) 3)

Demo shuffle

> (shuffle '(a b c d e f) 6)

Write shuffle

(define shuffle
  (lambda (deck size)
    (let ((half (quotient (+ size 1) 2)))
      (interleave (first-elements-of half deck)
                  (list-tail deck half)))))

Demo multiple-shuffle

> (multiple-shuffle '(a b c d e f) 6 2)

Write multiple-shuffle

(define multiple-shuffle
  (lambda (deck size times)
    (if (= times 0)
        deck
        (multiple-shuffle (shuffle deck size)
                          size (- times 1)))))

Demo map

> (sqrt 5)
> (sqrt (5 6 7)) ; Does not work
> (sqrt '(5 6 7)) ; Does not work
> (map sqrt '(5 6 7))
> (map (lambda (x) (< x 6)) '(5 6 7))

Demo add-to-end

> (add-to-end '(a b c d) 'x)
> (add-to-end () 'x)

add-to-end slides
=================

Write add-to-end

(define add-to-end
  (lambda (lst elt)
    (if (null? lst)    ; adding to an empty list
        (cons elt '()) ;  makes a one-element list
        (cons (car lst)
              (add-to-end (cdr lst) elt)))))

Demo my-reverse

> (my-reverse '(a b c d))
> (my-reverse ())

Write my-reverse using add-to-end

;; Inefficient version of reverse
(define my-reverse 
  (lambda (lst)  
    (if (null? lst) 
        '() 
        (add-to-end (my-reverse (cdr lst)) (car lst)))))

Slide, Efficiency of add-to-end

Slide, Efficiency of my-reverse

Slide, reverse-onto, your-reverse
Note, cannot demo reverse-onto as it is internal to your-reverse

(= '(a b c) '(a b c)) ; Does not work
> (equal? '(a b c) '(a b c))
> (equal? '(a b c) '(a x c))
> (equal? '(a b c) '(a b))
> (palindrome? '(a b c b a))
> (palindrome? '(a b b a))

Write palindrome? using reverse

Demo, note duplicates

> (merge-sort '(1 9 3 3 6 3 4))
> (merge '(2 4 6 8) '(1 3 5 8 9))

Show and discuss merge-sort

(define merge-sort
  (lambda (lst)
    (cond ((null? lst)
           '())
          ((null? (cdr lst))
           lst)
          (else
           (merge (merge-sort (one-part lst))
                  (merge-sort (the-other-part lst)))))))

Slide, merge

Write merge

(define merge
  (lambda (lst1 lst2)
    (cond ((null? lst1) lst2)
          ((null? lst2) lst1)
          ((< (car lst1) (car lst2))
           (cons (car lst1) (merge (cdr lst1) lst2)))
          ((= (car lst1) (car lst2))
           (cons (car lst1) (merge (cdr lst1) (cdr lst2))))
          (else
           (cons (car lst2) (merge  lst1 (cdr lst2)))))))

Demo

> (odd-part '(g i r a f f e))
> (even-part '(g i r a f f e))
> (one-part '(g i r a f f e))
> (the-other-part '(g i r a f f e))

Slide, odd-part

Write odd-part, even-part

(define odd-part
  (lambda (lst)
    (if (null? lst)
        '()
        (cons (car lst) (even-part (cdr lst))))))

(define even-part
  (lambda (lst)
    (if (null? lst)
        '()
        (odd-part (cdr lst)))))

Write one-part, the-other-part
(define one-part odd-part)
(define the-other-part even-part)

Slides, count-combos