Lab 9: Oobleck

1 Introduction(s)

You’ll work in labs in pairs. Find someone to work with for this first lab and introduce yourself.

Make sure at least one of you have a laptop to work on for this lab.

The two of you will work as a team to solve problems. At any time, one of you will be the Head and the other will be the Hands. The Head does the thinking and the Hands does the typing. Hands type only what the Head tells them to, but you’re free to discuss any issues that pop up. We’ll have you switch off during the lab to make sure each of you get practice problem solving, dealing with syntax, and getting finger exercises on the keyboard.

2 Purpose

In this lab, you’ll practice making templates and designing functions for complex data.

Royal Magicians

; A Shuffle is one of:

; - Duffle

; - Muzzle

; - Muff

;

; A Duffle is one of:

; - Number

; - String

;

(define-struct muzzle-town ())

(define-struct muzzle-street (oobleck tumble down))

; A Muzzle is one of:

; - (make-muzzle-town)

; - (make-muzzle-street String Shuffle Muzzle)

;

; A Muff is one of:

; - '()

; - (cons Shuffle Muff)

The interpretation is omitted intentionally. Since we don’t know anything about the meaning of this data, we must operate on Shuffles based on the structure alone. To do that, we’ll use templates.

If your partner hands you a Shuffle, you’ve got one of three things. To deal with that Shuffle, you need to know which of those three things you have! Any function you write has to know the same.

Let’s make three predicates for distinguishing each of these three kinds of things.

Lab problem 1: duffle?

Implement duffle? : Shuffle -> Boolean, which returns #true only if the given Shuffle is a Duffle.

Lab problem 2: muzzle?

Implement muzzle? : Shuffle -> Boolean, which returns #true only if the given Shuffle is a Muzzle.

Lab problem 3: muff?

Implement muff? : Shuffle -> Boolean, which returns #true only if the given Shuffle is a Muff.

Well-named predicates help keep functions on Shuffles intelligible.

Search and Destroy

; shuffle-template : Shuffle -> ???

; The form of every structural operation over Shuffles.

(define (shuffle-template s)

(cond [(duffle? s) (duffle-template s)]

[(muzzle? s) (muzzle-template s)]

[(muff? s) (muff-template s)]))

In Shuffles, as in all itemizations, we search through the possible cases with cond to figure out what to do with the Shuffle at hand. We then refer each case to the proper template for more specific handling, signaling where helper functions should appear in our code.

Lab problem 4: Duffle template

Duffles are itemizations as well. Define duffle-template, the form that all functions that operate on Duffles.

; duffle-template : Duffle -> ???

The muff-template is the template we’ve written time and time again. We have one of the two possible cases of the Muff itemization.

• If we find '() we’ll have to return something. What we return is entirely output-specific, so we indicate it with ....

• If we find a composite cons cell, we destroy it by tearing it apart. The smaller pieces are passed off to their respective templates for specific handling, signaling where helper functions should appear in our code.

; muff-template : Muff -> ???

; The form of all functions that operate on Muffs.

(define (muff-template m)

(cond [(empty? m) ...]

[(cons? m) (... (shuffle-template (first m))

...

(muff-template (rest m)) ...)]))

Lab problem 5: Muzzle template

Write down the template for all operations that consume a Muzzle. Be sure to include explicit applications of any necessary templates.

Working on Muzzles

Lab problem 6: Muzzle streets

Design a function count-streets that returns the number of Muzzle streets in a given Muzzle.

Hint: Make sure you check all the places a Muzzle can be found inside a Muzzle, it may require a helper function shuffle-streets.

(define MUZ0 (make-muzzle-town))

(define MUZ1 (make-muzzle-street "foo" 42 MUZ0))

(define MUZ2 (make-muzzle-street "bar" MUZ1 MUZ1))

(check-expect (count-streets MUZ0) 0)

(check-expect (count-streets MUZ1) 1)

(check-expect (count-streets MUZ2) 3)

Lab problem 7: Muzzle find

Design a function muzzle-find that is given a Muzzle and a string key. If the Muzzle contains a Muzzle street with key in the oobleck field, it returns the Shuffle in the tumble field. Otherwise, muzzle-find returns #false. (Hint: you may have to design a new data definition to handle this choice of outputs).

(check-expect (muzzle-find MUZ0 "foo") #false)

(check-expect (muzzle-find MUZ1 "bar") #false)

(check-expect (muzzle-find MUZ2 "foo") 42)

(check-expect (muzzle-find MUZ2 "bar") MUZ1)