On this page:
Hand-Rolled Lists (15 minutes)
Lists (55 minutes)
Code Review (30 minutes)
Before You Go...

3 Lists

home work!

Purpose: The purpose of this lab is to give you some hands-on experience with list-processing functions. When you walk out of this lab, you should understand a variety of list-based data definitions and how to design functions for these.

Textbook references: Chapter 8: Lists, Chapter 9: Designing with Self-Referential Data Definitions, Chapter 10.2: Structures in Lists

Hand-Rolled Lists (15 minutes)

Goals: Practice creating and processing self-referential data.

Sample Problem Develop a data definion for hand-rolled lists of numbers.

(define-struct empty-lon [])
(define-struct cons-lon [left right])
; A HRLoN (Hand-rolled List of Numbers) is one of:
; - (make-empty-lon)
; - (make-cons-lon Number HRLoN)

Sample Problem Create three examples of HRLoNs.

; Examples
(define HRLON1 (make-empty-lon))
(define HRLON2 (make-cons-lon 3 HRLON1))
(define HRLON3 (make-cons-lon 4 (make-cons-lon 7 HRLON2)))

Sample Problem Develop a template for functions that process HRLoNs.

; HRLoN -> ???
(define (hrlon-temp ahrlon)
  (cond [(empty-lon? ahrlon) ...]
        [(cons-lon? ahrlon)
         ... (cons-lon-left ahrlon) ...
         ... (hrlon-temp (cons-lon-right ahrlon)) ...]))

Sample Problem Design the function hrlon-sum which computes the sum of a hand-rolled list of numbers.

; HRLoN -> Number
; computes the sum of a hand-rolled list of numbers
(check-expect (hrlon-sum HRLON1) 0)
(check-expect (hrlon-sum HRLON2) 3)
(check-expect (hrlon-sum HRLON3) 14)
(define (hrlon-sum ahrlon)
  (cond [(empty-lon? ahrlon) 0]
        [(cons-lon? ahrlon)
         (+ (cons-lon-left ahrlon)
            (hrlon-sum (cons-lon-right ahrlon)))]))

Lists (55 minutes)

Goals: Practice defining and processing lists.

Good news, everyone. We just got word from upstairs that all the components of lists are working again! Now this Hand-rolled List of Numbers thing seems a bit unnecessary. Before proceeding with the following exercises, develop a new data-definition for a List of Numbers, using cons and ’().

Exercise 1 The Northeastern Zoo has hired you as its animal caretaker, and one of your jobs is to ensure that all the animals are fed properly. An Animal has a name, an age, and a non-empty list of favorite foods, as seen in the data definitions provided below. Design the function shopping-list that consumes a list of Animals and produces a list of all the Animals’ favorite foods. Do not worry about repeats.

; A Non-Empty-List-of-String (NELOS) is one of:
; - (cons String '())
; - (cons String NELOS)
(define-struct animal [name age foods])
; An Animal is a (make-animal String Number NELOS) where
; - name is the animal's name
; - age is the animal's age in years
; - foods is a non-empty list of the animal's favorite foods
(define ANIMAL1-FOOD (cons "cereal" (cons "milk" '())))
(define ANIMAL1 (make-animal "Terry the Tiger" 2 ANIMAL1-FOOD))
(define ANIMAL2-FOOD (cons "shrimp" '()))
(define ANIMAL2 (make-animal "Florence Flamingo" 30 ANIMAL2-FOOD))
(define ANIMAL3-FOOD
  (cons "spinach"
    (cons "walnuts"
      (cons "balsamic viniagrette" '()))))
(define ANIMAL3 (make-animal "Samantha Stickbug" 8 ANIMAL3-FOOD))

Exercise 2 Design the function reflect-xy that consumes a list of Posns and translates (reflects) them across both the x and y axes.

Domain Knowledge From the MathBitsNotebook, "reflect over the y = x: When you reflect a point across the line y = x, the x-coordinate and y-coordinate change places."

Exercise 3 Design the function draw-skyline, which takes a list of Buildings and draws them all next to each other. (Hint: Check out the function beside/align.) The data definition for a Building is provided below.

(define-struct building [width height color])
; A Building is a (make-building Number Number Color) where
; - width is building's width in meters
; - height is the building's height in meters
; - color is the building's color
(define BUILDING1 (make-building 30 100 "black"))
(define BUILDING2 (make-building 60 15 "green"))
(define BUILDING3 (make-building 47 80 "pink"))

Challenge Exercise 4 Design the function animal-names that consumes a list of Animals and produces a String of all the Animals’ names, separated by a comma and a space.

(define LOA1 (cons ANIMAL1 '()))
(define LOA2 (cons ANIMAL2 LOA1))
(define LOA3 (cons ANIMAL3 LOA2))
(check-expect (animal-names LOA1) "Terry the Tiger")
(check-expect (animal-names LOA3)
              "Samantha Stickbug, Florence Flamingo, Terry the Tiger")

Code Review (30 minutes)

The Teaching Assistants will pick two pairs who will explain a solution to their lab mates following the design recipe steps.

Before You Go...

If you had trouble finishing any of the exercises in the lab or homework, or just feel like you’re struggling with any of the class material, please feel free to come to office hours and talk to a TA or tutor for additional assistance.