Module 9 Lists

Plane row example

A structure to hold an element and other elements in the list

(cons item list)

A representation of an empty list

'()

Predicates to distinguish an empty list from a list structure

(empty? any)
(cons? any)

Given a list structure, selectors for element/others

(first (cons item list)) ==> item
(rest (cons item list)) ==> list

Predicate to identify list (empty or not)

(list? any)

Example: `sum-list`, returns the sum of numbers

Design the function sum-list that accepts a list of numbers and returns the sum.

First, complete the design recipe for ListOfNumbers:

;; A LON is one of:
;; - '()
;; - (cons Number LON)
;; Interpretation: a list of numbers

(define LON-0 '())
(define LON-1 (cons 1 LON-0))
(define LON-2 (cons 5 LON-1))
(define LON-3 (cons -3.5 LON-2))

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

Then make the function:

;; sum-list : LON -> Number
;; Returns the sum of numbers in a list

(check-expect (sum-list LON-0) 0)
(check-expect (sum-list LON-2) 6)
(check-expect (sum-list LON-3) 2.5)

(define (sum-list lon)
  (cond
    [(empty? lon) 0]
    [(list? lon) (+ (first lon)
                    (sum-list (rest lon)))]))

Example: string lists

Design the function contains-alice? that determines whether a list of strings contains the word alice.

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

(define LOS-0 '())
(define LOS-1 (cons "Hello" LOS-0))
(define LOS-2 (cons "alice" LOS-1))
(define LOS-3 (cons "goodbye" LOS-2))

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

;; contains-alice? : LOS -> Boolean
;; Determines if a list of strings contains "alice"

(check-expect (contains-alice? LOS-0) #false)
(check-expect (contains-alice? LOS-1) #false)
(check-expect (contains-alice? LOS-2) #true)
(check-expect (contains-alice? LOS-3) #true)

(define (contains-alice? los)
  (cond
    [(empty? los) #false]
    [(cons? los) (or (string=? (first los) "alice")
                     (contains-alice? (rest los)))]))

Example: max distance from origin

Design the function max-distance-from-origin that accepts a list of positions and determines the maximal distance of any position from the origin.

Example: post and threads

Practice with Lists of Complex Data (Templates)

MessageBoard

name
threads: ListOfThreads
- thread: Thread
  - title
  - pinned?
  - post: Post
  - replies: ListOfPosts
    - post: Post
      - user
      - body