Lab 10 Processing Two Complex Inputs

Purpose: The purpose of this lab is to provide you with some more practice with processing two complex inputs.

Motivation

Have you ever considered how DrRacket actually makes check-expect work? It clearly has to check whether the inputs and outputs are the "same", in some manner, so that equal values make for a passing test. But how can we check larger data definitions for "equality"?

Sample Problem Consider the following data definition:

; A NumBT is one of:

; - Number

; - (make-node NumBT NumBT)

(define-struct node [left right])

Design the function same-tree? that takes two NumBTs and produces true if they have the same numbers in the same places. First, work through the template for two structured inputs.

(define (two-nbt-temp nbt1 nbt2)

; There are two cases for nbt1, and two cases for nbt2.

; The template needs to test for each possible combination

(cond

[(and (number? nbt1) (number? nbt2)) ...] ; both atomic

[(and (number? nbt1) (node? nbt2))        ; one is structured

(... nbt1 ... (node-left nbt2) ... (node-right nbt2))]

[(and (node? nbt1) (number? nbt2))        ; the other is structured

(... (node-left nbt1) ... (node-right nbt1) ... nbt2)]

[(and (node? nbt1) (node? nbt2))          ; both structured

(... (node-left nbt1) ... (node-right nbt1)

(node-left nbt2) ... (node-right nbt2))]))

Next design examples and use them to work through the function itself.

(define NBT1 (make-node 12 37))

(define NBT2 (make-node 13 (make-node 43 21)))

(define NBT3 (make-node NBT2 NBT1))

; same-tree? : NumBT NumBT -> Boolean

; Are these trees the same?

(check-expect (same-tree? NBT1 NBT2) #false)

(check-expect (same-tree? NBT3 NBT3) #true)

(check-expect (same-tree? NBT1 (make-node 12 37)) #true)

(define (same-tree? nbt1 nbt2)

(cond [(and (number? nbt1) (number? nbt2))

(= nbt1 nbt2)]

[(and (number? nbt1) (node? nbt2)) #false]

[(and (node? nbt1) (number? nbt2)) #false]

[(and (node? nbt1) (node? nbt2))

(and (same-tree? (node-left nbt1) (node-left nbt2))

(same-tree? (node-right nbt1) (node-right nbt2)))]))

Exercises

Exercise 1 Design the function add-trees, that takes two NumBTs of the same shape, and produces a new tree whose numbers are the sum of corresponding numbers in the two inputs. (If the two trees are different shapes, add-trees should error.)

Exercise 2 Consider the data definitions from Assignment 11a:

; A Road is one of:

; - 'dead-end

; - (make-straightaway String PositiveNumber Road)

; - Intersection

(define-struct straightaway [name distance more])

; INTERPRETATION: A road with some name and some amount of distance

; until the next portion of road

; An Intersection is a [List-of Road]

Design the function same-roads?, that takes two Roads and returns true if the two Roads have the same names, same distances, and same intersections. Two intersections should be considered the same if they have the same roads in the same order. (Hint! Consider carefully what the templates should be in this function — what should you do in the Intersection case? You may need another same-??? function...)

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.