What is Computer Science?
Computer science is to computers as microscopes are to biology.
This course is about how to solve problems, NOT how to use the tools to solve problems. Learning universal computer science and not the tools.
The course website is on canvas
Piazza:
Homework:
Like the order of operations but for computer science
This is an example of incorrect syntax
Shows how to go from a valid arithmetic expression to an answer.
\[5 \times 7 + \frac{21}{3}\]Why does this equal 42?
Breakdown:
\[35 + \frac{21}{3}\] \[35+7=42\]Example:
\[3x-2\]Can’t tell what this is yet because it’s not complete
Let $x=8$
Now it is 22 (because $3(8) -2=22$)
Do the assigned reading before the week (lightly). Once the lecture is over, go back and read the book.
How to read a technical book:
You can’t read it as a ‘normal’ book. Type along with the examples. Try out different variations of the presented code
Use the ‘Beginning Student Language’
Recall:
Dr Racket is split up into two panels, the top one is used for code that you want to keep and the bottom one can be thought of as interactive (it runs each line when you hit enter)
(replicate 10 "hi ")
; "hi hi hi hi hi hi hi hi hi hi "
Import Library:
(require 2htdp/image)
(circle 10 "solid" "red") ; returns a solid, red circle of radius 10
(rectange 300 200 "outline" "blue") ; Returns rectangle width 300,
;height 200
Other Functions of Images
(beside [image1] [image2])
(overlay [image1] [image2])
NOTE: Both of these functions return an image (you can nest these functions)
place-image
(place-image IMAGE x y scene) ; see documentation for more
NOTE: The origin point is the top left corner
Example:
; Create an image of a setting sun with a blue background
(circle 30 "solid" "yellow") ; sun
(rectangle 300 200 "solid" "blue") ; sky
(place-image (circle 10 "solid" "yellow") 40 50
(rectangle 400 200 "solid" "blue")
This code is ugly and doesn’t represent how humans think about. We assign names to things. For example (circle 10 "solid" "yellow") is the sun. To do this, we use the define function.
Example:
(define SUN (circle 10 "solid" "yellow"))
(define SKY (rectangle 400 200 "solid" "blue"))
(place-image SUN 300 500 SKY)
What is a function?
\[f(t)=30 - \frac{1}{2}9.8^{2}\]This function explains how far an object will have gone t seconds after dropping.
There are 3 things abou thtis function
(define ([name] [argument[s]) (body of the function))
Example:
(define ACCEL-BY-GRAVITY 9.8)
(define (free-fall t)
(- 30 (* (/ 1 2) ACCEL-BY-GRAVITY t t))
Example: Example drawing function in DrRacket
; Draw a sun with y-point `y`
(define (draw-sun y)
(place-image SUN 300 y SKY))
But what about ‘real’ animations?
; Include draw-sun function from previous example
(require 2htdp/universe)
(animate draw-sun) ; Input a function that will be incremented every
; tick
Recall this math equation from Lecture 2 - Intro to Dr Racket and Image Manipulation
\[f(t) = 30 - \frac{1}{2} 9.8^{2}\]; whole program not shown
(define (free-fall t)
(-30 (* 1/2 ACCEL-BY-GRAVITY t t)))
Solving By Substitution
Racket replaces all variables by the actual parameter/variable value. If you put in 3 into free-fall, it would handle it as follows
(- 30 (* 1/2 9.8 3 3)) = -14.1
Whenever you write $\frac{1}{2}$or $\frac{1}{3}$, you aren’t doing the division (the language handles it as a single number). To actually do the division, do (/ 1 2)
Block Comments: #| [CODE] |#
Single Line: ;
Checks return value against an expected value. Shows ‘halloween’ colors where your code hasn’t run in the tests.
(check-expect [function with value] [expected value])
For example:
(check-expect (price->yelp 100) "$$$") ; Returns 'The test passed!'
Shows how BSL uses substitiution in its code. Acts as a debugger.
$f(t) = 30 - \frac{1}{2} 9.8^{2}$
Any yes/no or true/false answer. In BSL, they are represented by #true and #false
A function that returns a boolean. Usually ends with ? and it’s pronounced ‘huh’. Example string? is pronounced string-huh?
(require 2htdp/image)
(require 2htdp/universe)
(define SUN (circle 10 "solid" "yellow"))
(define SKY (rectangle 200 100 "solid" "blue"))
(define NIGHT-SKY (rectangle 200 100 "solid" "black"))
(define MOON (circle 10 "solid" "gray"))
(place-image 100 33 SUN 100 33 SKY)); Places the SUN in the SKY
(place-image MOON 50 33 (place-image SUN 100 33 SKY)); Places the moon and sun in the sky
; Places the moon at the given x
; coordinate on an image of the sun and the sky.
; eclipse: Number -> Image
(define (eclipse moon-x)
(place-image MOON moon-x 33 (place-image SUN 100 33 SKY)))
(animate eclipse); Run and incriment eclipse every `tick'
Now let’s try to write the eclipse function with a conditional (See later in the lecture for conditionals)
; Places the moon at the given x
; coordinate on an image of the sun and the sky.
; eclipse: Number -> Image
(define (eclipse moon-x)
(place-image MOON moon-x 33 (place-image SUN 100 33
(cond
[ ..to the left.. SKY]
[ ..covering.. NIGHT-SKY]
[ ..to the right.. SKY]))))
(animate eclipse); Run and incriment eclipse every `tick'
Goes through the tests until one of them is true, then it runs the corresponding code.
(cond
[test-1 answer-1]
[test-2 answer-2])
Example: price->yelp
; price->yelp (pronounced "price to yelp")
(define (price-> price)
(cond
[(> price 50) "\$\$\$\$"]
[(> price 30) "\$\$\$"]
[(> price 15) "\$\$"]
[(< price 15) "\$"]))
; if you don't want the last check,
;use `else' in the condititon to catch everything else
From Lecture 3’s class:
(require 2htdp/image)
(require 2htdp/universe)
(define SUN (circle 25 "solid" "yellow"))
(define MOON (circle 25 "solid" "gray"))
(define SKY (rectangle 200 200 "solid" "light blue"))
(define NIGHT-SKY (rectangle 200 200 "solid" "black"))
; draw-eclipse : Number -> Image
; Draw the moon at the given x-coordinate, on a scene with the
(define (draw-eclipse x-moon)
(place-image MOON x-moon 100 (place-image SUN 100 100 (cond
[test-2 SKY]
[test-2 NIGHT-SKY]))))
(animate draw-eclipse)
Examples:
(cond
[test-2 SKY]
[test-2 NIGHT-SKY])
Notice how each condition is on its own line and they are properly indented
(require 2htdp/image)
(require 2htdp/universe)
(define SUN (circle 25 "solid" "yellow"))
(define MOON (circle 25 "solid" "gray"))
(define SKY (rectangle 200 200 "solid" "light blue"))
(define NIGHT-SKY (rectangle 200 200 "solid" "black"))
(define DARK-SKY (rectangle 200 200 "solid" "blue"))
; draw-eclipse : Number -> Image
; Draw the moon at the given x-coordinate, on a scene with the
(define (draw-eclipse x-moon)
(place-image
MOON
x-moon
100
(place-image
SUN
100
100
(cond
[(or (< x-moon 50) (> x-moon 150)) SKY]
[(= x-moon 100) NIGHT-SKY]
[(<= 50 x-moon 150) DARK-SKY])))) ; between 50 - 100 - 150
(animate draw-eclipse)
check-expectsDesigning Functions:
Designing Data:
Prompt: Create a function that takes in a numerical grade and returns a letter grade
Signature: num->grade : Number -> String Can be multiple lines to define data types
Purpose Statement: Given a numeric grade, produces a letter grade
Function Template: Used to copy and paste for similar functions (such as lettergrade->gpa, lettergrade->passing?)
; letter-grade-template : LetterGrade -> ?
#| (define (letter-grade-template lg)
(cond
[(string=? lg "A") ...]
[(string=? lg "B") ...]
[(string=? lg "C") ...]
[(string=? lg "D") ...]
[(string=? lg "F") ...]))
|# ;This is a block comment
Examples (check-expects): Examples of what inputs lead to what outputs
The Funtion Body: the function itself
; A NumericGrade is a real number in [0,100]
; Interpretation: A student's numeric grade in Fundies I.
; A LetterGrade is a one of
; - "A"
; - "B"
; - "C"
; - "D"
; - "F" ; An enumerated data definition
; Interpretation: A student's letter grade is Fundies I.
; num->grade : NumericGrade -> LetterGrade
; Given a numeric grade, produces a letter grade
(check-expect (num->grade 93) "A")
(check-expect (num->grade 88) "B")
(check-expect (num->grade 72) "C")
; Unreasonable Examples
(check-expect (num->grade -10) "F")
(check-expect (num->grade 101) "A")
(define (num->grade n)
(cond
[(>= n 90) "A"]
[(>= n 80) "B"]
[(>= n 70) "C"]
[(>= n 60) "D"]
[(< n 40) "F"]))
; A LetterGrade is a one of
; - "A"
; - "B"
; - "C"
; - "D"
; - "F"
; Given a letter grade, determine if it is a passing grade.
; grade->passing? : LetterGrade -> Boolean
(define (grade->passing? lg)
(cond
[(string-equals? lg "A") #true]
[(string-equals? lg "B") #true]
[(string-equals? lg "C") #true]
[(string-equals? lg "D") #false]
[(string-equals? lg "F") #false]))
Two things you need to design for a program: - Data - You will rarely need to accept all numbers. It’s a subset of all real numbers (ℕ). Examples of this are GPA’s are between 0 and 4 - Functions
Example: convert temperature from celcius to fahrenheit
Note: use VAR to represent the variable ‘VAR’ in comments. Essentially quotation marks
; Celcius is a Number greater than or equal to -273
; Interpretation: A temperature expressed in celcius.
(define celcius-ex-freezing 0 )
(define celcius-ex-boiling 100)
; celcius-template : Celcius -> ?
(define (celcius-template ctemp)
(... ctemp ...))
; Not too much info can be given in the template, but use ctemp
; Fahrenheit is a Number greater than or equal to -460
; Interpretation: A tempature expressed in fahrenheit
(define fahrenheit-ex-freezing 32)
(define farhrenheit-ex-boiling 212)
; fahrenheit-template : Fahrenheit -> ?
(define (fahrenheit-template ftemp)
(... ftemp ...)) ; Not useful now, but just in case fahrenheit is the input
; c->f : Celcius -> Fahrenheit
; Converts the given _ctemp_ in celcius to a
; temperature in fahrenheit.
(check-expect (c->f celcius-ex-freezing) fahrenheit-ex-freezing)
(check-expect (c->f celcius-ex-boiling) farhrenheit-ex-boiling)
(define (c->f ctemp)
(+ (* (/ 9 5) ctemp) 32))
Example 2: Design a traffic light
(require 2htdp/image)
; A TrafficLight is a:
; - "Red"
; - "Yellow"
; - "Green"
; Interpretation: The color of the active lightbulb in a standard U.S. traffic light.
(define TL-RED "Red") ; Constants are used to you don't make capitalization mistakes
(define TL-YELLOW "Yellow")
(define TL-GREEN "Green")
; tl-template : TrafficLight -> ?
;(define (tl-template tl)
; (cond
; [(string=? tl TL-RED) test-1 ...]
; [(string=? tl TL-YELLOW) test-2 ...]
; [(string=? tl TL-GREEN) test-3 ...]))
; Takes a __TrafficLight__ and returns an image of the corresponding light (__TrafficImage__)
; A TrafficImage is a circle with color red, yellow, or green
; draw-traffic-light : TrafficLight -> TrafficImage
(check-expect (draw-light TL-RED) (circle 40 "solid" "red"))
(define (draw-traffic-light tl)
(circle 40 "solid" tl))
(draw-traffic-light TL-GREEN)
; ran out of time for the signature :/
(define (next-light tl)
(cond
[(string=? tl TL-RED) TL-GREEN]
[(string=? tl TL-YELLOW) TL-RED]
[(string=? tl TL-GREEN) TL-YELLOW]))
HW 2 - Do with the same partners at HW1
Writing a function that handles TrafficLights
Datatype TrafficLight is an enumerated data list with three different possible String possibilities
Functions:
next-light - Given a traffic light, return the next color
animate because it returns an incremented number which isn’t compatable with the TrafficLight datatypeso instead we have to use…
Example:
(big-bang
TL-RED ; Initial State
[on-draw draw-light] ; Do this event every tick)
[on-tick next-light] 0.25) ; What to do every tick (incrementation
; The 0.25 denotes the rate of animation
How Big-Bang works (it requires 2htdp/universe)
on-draw on initial stateon-tick creates new scene with given stateReturn a full image of traffic light with all colors and have the active on solid (with the others outlined)
Example:
Draw a TrafficLight bulb with color tl and the corresponding outlined/solid
If you have a cond with only two possibilities, use an if statement which is structured as follows: (if (condition) (IF_TRUE) (IF_FALSE))
; Draw a traffic light blub with color _tl_, that is either on or off, depending
; on the color of the active light.
; (string=? tl active-tl)
(define (draw-bulb/v2 tl active-tl)
(circle
30
(if (string=? tl active-tl)
"solid"
"outline")
tl))
Full Code from Class:
(require 2htdp/image)
(require 2htdp/universe)
; A TrafficLight is a:
; - "Red"
; - "Yellow"
; - "Green"
; Interpretation: The color of the active lightbulb in a standard U.S. traffic light.
(define TL-RED "Red")
(define TL-YELLOW "Yellow")
(define TL-GREEN "Green")
; tl-template : TrafficLight -> ?
(define (tl-template tl)
(cond
[(string=? tl TL-RED) ...]
[(string=? tl TL-YELLOW) ...]
[(string=? tl TL-GREEN) ...]))
; A TrafficImage is a circle with color red, yellow, or green
; draw-light : TrafficLight -> Image
; Given a traffic light, produces an image of the traffic light.
(check-expect (draw-light TL-RED) (circle 30 "solid" "Red"))
(define (draw-light tl)
(cond
[(string=? tl TL-RED) (circle 30 "solid" "red")]
[(string=? tl TL-YELLOW) (circle 30 "solid" "yellow")]
[(string=? tl TL-GREEN) (circle 30 "solid" "green")]))
(define (draw-light/v2 tl)
(circle 30 "solid"
(cond
[(string=? tl TL-RED) "red"]
[(string=? tl TL-YELLOW) "yellow"]
[(string=? tl TL-GREEN) "green"])))
(define (draw-light/v3 tl)
(circle 30 "solid" tl))
; Given a TrafficLight, produce a TrafficLight that represents
; the next color of a traffic light in the standard sequence.
; next-light : TrafficLight -> TrafficLight
(check-expect (next-light TL-RED) TL-GREEN)
(check-expect (next-light TL-YELLOW) TL-RED)
(check-expect (next-light TL-GREEN) TL-YELLOW)
(define (next-light tl)
(cond
[(string=? tl TL-RED) TL-GREEN]
[(string=? tl TL-YELLOW) TL-RED]
[(string=? tl TL-GREEN) TL-YELLOW]))
;(big-bang
; TL-RED
; [on-draw draw-light/v3]
; [on-tick next-light 0.25])
; draw-light/v4 : TrafficLight -> Image
; Draws a traffic light, with the active bulb lit and the two inactive blubs dimmed.
(define red-light-ex
(above
(circle 15 "solid" "red")
(circle 15 "outline" "yellow")
(circle 15 "outline" "green")))
(define yellow-light-ex
(above
(circle 15 "outline" "red")
(circle 15 "solid" "yellow")
(circle 15 "outline" "green")))
; Draw a traffic light blub with color _tl_, that is either on or off, depending
; on the color of the active light.
; (string=? tl active-tl)
(define (draw-bulb/v1 tl active-tl)
(circle 30 "solid" tl))
(define (draw-bulb/v2 tl active-tl)
(circle
30
(if (string=? tl active-tl)
"solid"
"outline")
tl))
(check-expect
(draw-bulb/v2 TL-RED TL-RED)
(circle 30 "solid" "red"))
(check-expect
(draw-bulb/v2 TL-RED TL-GREEN)
(circle 30 "outline" "red"))
;(define (draw-light/v4 tl)
; (above
; (cond
; [(string=? tl TL-RED)
; (circle 15 "solid" "red")
; (circle 15 "outline" "yellow")
; (circle 15 "outline" "green")]
; [(string=? tl TL-YELLOW)
; (circle 15 "outline" "red")
; (circle 15 "solid" "yellow")
; (circle 15 "outline" "green")]
; [(string=? tl TL-GREEN) ...]))
(define (draw-light/v4 tl)
(above
(draw-bulb/v2 TL-RED tl)
(draw-bulb/v2 TL-YELLOW tl)
(draw-bulb/v2 TL-GREEN tl)))
(big-bang
TL-RED
[on-draw draw-light/v4]
[on-tick next-light 0.25])
HW: Give at least 3 ‘interseting’ examples
Information vs. Data: Information is the interpretation of data
BAD WAY of representing this data:
"Jane Doe 3.9 #false"
This is bad because it’s all in a single string. Someone with a first name with a space in it can break it. For example:
"Jin Ho Kim 3.9 #false"
(define-struct student [first last gpa on-coop])
Creates ‘constructor’ function that tkes 4 arguments (which correspond to the 4 inputs)
Example:
(make-student "Jin Ho" "Kim" 3.9 #false) ; This is an extual value
Accessor functions are also created
(student-first example-student-1) ; returns the first name of __example-student-1__
Wait! What if we did (make-student student 0 0 0 0), after all, those are four inputs.
This is why we need a good data definition
; A GPA is a Number in the range [0.0, 4.0]
; Data definition:
; A student is a _(make-student String String GPA Boolean)_
;
; Interpretation: A _(make-student first last gpa on-coop)_
; represents a student with name _first last_ and GPA _gpa_, and
; _on-coop_ is _#true_ if they are presently on a co-op.
(define-struct student [first last gpa on-coop])
What does a template for a studentlook like?
; student-template : student -> ?
(define (student-template student)
(... (student-first student) ...
(student-last student) ...
(student-gpa student) ...
(student-on-coop student) ...))
You can’t change a structure, so functions have to return a different structure.
Example:
; toggle-coop : student -> student
; _(toggle-coop s)_ consumes a student _s_ and produces student
; that that is identical to _s_, but with the opposite co-op
; status.
(define (toggle-coop student)
(make-student
(student-first student)
(student-last student)
(student-gpa student)
(not (student-on-coop student))))
; Data definition:
; A ball is a (make-ball Real Real Real Real)
; Interpretation:
; A _(make-ball x y vx vy)_ represents a ball at position (x,y)
; moving with velocity (vx, vy).
(define-struct ball [x y vx vy])
(define (ball-template b)
(... (ball-x b) ...
(ball-y b) ...
(ball-vx b) ...
(ball-vy b) ...))
; move-ball : ball -> ball
(define (move-ball b)
(make-ball
(+ (ball-x b) (ball-vx b))
(+ (ball-y b) (ball-vy b))
(ball-vx b)
(ball-vy b)))
(define ball-example-1 (make-ball 0 0 10 0))
(check-expect (move-ball ball-example-1)
(make-ball 10 0 10 0))
(define ball-example-2 (make-ball 3 7 5 10))
(check-expect (move-ball ball-example-2)
(make-ball (+ 3 5) (+ 7 10) 5 10))
(check-expect (ball-vx ball-example-1) 10)
(make-ball 1+2i "hi" #true 5)
(require 2htdp/image)
(require 2htdp/universe)
; draw-ball : ball -> Image
(define (draw-ball b)
(place-image
(circle 10 "solid" "red")
(ball-x b)
(ball-y b)
(rectangle 200 200 "solid" "white")))
Full Lecture Code
; Kinds of data:
; - Atomic data, e.g., strings, booleans, numbers
; - Intervals, e.g., ranges of numbers
; - Enumerated data, e.g. TrafficLight
; - Structured data
; Data definition that represents first name, last
; last, GPA, and on-coop-or-not
(define bad-example-student
"Jin Ho Kim 3.9 #false")
; A GPA is a Number in the range [0.0, 4.0]
; Data definition:
; A student is a _(make-student String String GPA Boolean)_
;
; Interpretation: A _(make-student first last gpa on-coop)_
; represents a student with name _first last_ and GPA _gpa_, and
; _on-coop_ is _#true_ if they are presently on a co-op.
(define-struct student [first last gpa on-coop])
(define example-student-2
(make-student "Arjun" "Guha" 3.4 #false))
; student-template : student -> ?
(define (student-template student)
(... (student-first student) ...
(student-last student) ...
(student-gpa student) ...
(student-on-coop student) ...))
; toggle-coop : student -> student
; _(toggle-coop s)_ consumes a student _s_ and produces student
; that that is identical to _s_, but with the opposite co-op
; status.
(define (toggle-coop student)
(make-student
(student-first student)
(student-last student)
(student-gpa student)
(not (student-on-coop student))))
(define example-student-1
(make-student "Jin Ho" "Kim" 3.9 #false))
(check-expect (toggle-coop example-student-1)
(make-student "Jin Ho" "Kim" 3.9 #true))
; Accessor
(student-gpa example-student-1)
; Data definition:
; A ball is a (make-ball Real Real Real Real)
; Interpretation:
; A _(make-ball x y vx vy)_ represents a ball at position (x,y)
; moving with velocity (vx, vy).
(define-struct ball [x y vx vy])
(define (ball-template b)
(... (ball-x b) ...
(ball-y b) ...
(ball-vx b) ...
(ball-vy b) ...))
; move-ball : ball -> ball
(define (move-ball b)
(make-ball
(+ (ball-x b) (ball-vx b))
(+ (ball-y b) (ball-vy b))
(ball-vx b)
(ball-vy b)))
(define ball-example-1 (make-ball 0 0 10 0))
(check-expect (move-ball ball-example-1)
(make-ball 10 0 10 0))
(define ball-example-2 (make-ball 3 7 5 10))
(check-expect (move-ball ball-example-2)
(make-ball (+ 3 5) (+ 7 10) 5 10))
(check-expect (ball-vx ball-example-1) 10)
(make-ball 1+2i "hi" #true 5)
(require 2htdp/image)
(require 2htdp/universe)
; draw-ball : ball -> Image
(define (draw-ball b)
(place-image
(circle 10 "solid" "red")
(ball-x b)
(ball-y b)
(rectangle 200 200 "solid" "white")))
(define ex-x 3)
(define ex-y 7)
(define ball-example-2/v2 (make-ball ex-x ex-y 5 10))
Recall from Lecture 7 - Structures
Structures are values that you can think of as a box with ‘n’ number of compartments (‘n’ is the number of inputs you spesifiy)
The difference between value and expression
Value: The data
Expression: A task for the computer to simplify further (ex. (+ 1 2))
NOTE: Values are expressions
13, returns 13define-struct
student? (replace with structure name) is a predicate that returns if a value is of type student (or whatever other structure)
; student-template : student -> ?
(define (student-template student)
(... (student-first student) ...
(student-last student) ...
(student-gpa student) ...
(student-on-coop student) ...))
We want to make a function move-ballthat moves the ball. Every call, add the velocity to the position for the new position.
Remember: You don’t need to use every attribute of ball (structure) for every funciton
draw-ball doesn’t use the velocityDO NOT DO THIS:
(define-struct two-balls [x1 y1 vx1 vy1 x2 y2 vx2 vy2]))
As programmers, we want to reuse code (plus this is ugly to read)
Instead do:
(define-struct two-balls [ball1 ball2])
This allows you to do this:
(make-two-balls example-ball-1 example-ball-2) ; Nested structure
It is uncommon to have structure names with hyphens
two-balls; two-balls-template : Two-Balls -> ?
(define (two-balls-template tb)
(... (ball-template (two-balls-ball1 tb)) ...
(ball-template (two-balls-ball2 tb)) ...))
You don’t have to understand everything at any given time
draw-two-ballsdraw-ball; draw-two-balls : Two-Balls -> Image
(define (draw-two-balls tb)
(... (draw-ball (two-balls-ball1 tb)) ...
(draw-ball (two-balls-ball2 tb)) ...))
This doesn’t work right now because both balls have backgrounds (that aren’t transparent)
Lecture 8 Code
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Based on code from Lecture 7.
(require 2htdp/image)
(require 2htdp/universe)
(define bad-student-example "Phyo Ba Kyu 3.1 #false")
;; A GPA is a Number in the range [0.0, 4.0].
;; A Student is a _(make-student String String GPA Boolean)_
;;
;; Interpretation: A _(make-student first last gpa on-coop)_ represents a
;; student with name _first last_ and GPA _gpa_. The boolean _on-coop_ indicates
;; whether or not the student is presently on a co-op.
(define-struct student [first last gpa on-coop])
(define example-student-1 (make-student "Arjun" "Guha" 3.4 #false))
(define example-student-2 (make-student "Phyo" "Ba Kyu" 3.1 #true))
;; student-template : student -> ?
(define (student-template student)
(... (student-first student) ...
(student-last student) ...
(student-gpa student) ...
(student-on-coop student) ...))
;; A Ball is a _(make-ball Real Real Real Real)_.
;;
;; Interpretation: A _(make-ball x y vx vy)_ represents a ball at position
;; (_x_,_y_), moving with velocity (_vx_, _vy_).
(define-struct ball [x y vx vy])
;; A Ball at the origin, moving horizontally.
(define ball-example-1 (make-ball 100 100 10 0))
;; A Ball moving diagonally, going up faster than it is moving right.
(define ball-example-2 (make-ball 25 25 5 10))
(define (ball-template b)
(... (ball-x b) ...
(ball-y b) ...
(ball-vx b) ...
(ball-vy b) ...))
;; move-ball : Ball -> Ball
(define (move-ball b)
(make-ball
(+ (ball-x b) (ball-vx b))
(+ (ball-y b) (ball-vy b))
(ball-vx b)
(ball-vy b)))
;(check-expect (move-ball ball-example-1) (make-ball 10 0 10 0))
;(check-expect (move-ball ball-example-2) (make-ball (+ 3 5) (+ 7 10) 5 10))
(define BACKGROUND (rectangle 200 200 "solid" "grey"))
;; draw-ball : Ball -> Image
;; Draws a ball on _BACKGROUND_.
(define (draw-ball b)
(place-image (circle 10 "solid" "red") (ball-x b) (ball-y b) BACKGROUND))
;; A Two-Balls is a _(make-two-balls Ball Ball)_.
;; Interpretation: A Two-Balls represents two balls moving independently.
(define-struct two-balls [ball1 ball2])
(define ex-tb-1 (make-two-balls (move-ball ball-example-2) ball-example-1))
; two-balls-template : Two-Balls -> ?
(define (two-balls-template/v1 tb)
(... (two-balls-ball1 tb) ...
(two-balls-ball2 tb) ...))
(define (two-balls-template/v2 tb)
(... (ball-x (two-balls-ball1 tb)) ...
(ball-y (two-balls-ball1 tb)) ...
; etc.
(two-balls-ball2 tb) ...))
(define (two-balls-template tb)
(... (ball-template (two-balls-ball1 tb)) ...
(ball-template (two-balls-ball2 tb)) ...))
; move-two-balls : Two-Balls -> Two-Balls
(define (move-two-balls tb)
(make-two-balls
(move-ball (two-balls-ball1 tb))
(move-ball (two-balls-ball2 tb))))
(check-expect (move-two-balls (make-two-balls ball-example-1 ball-example-2))
(make-two-balls (move-ball ball-example-1)
(move-ball ball-example-2)))
#|
(move-two-balls (make-two-balls ball-example-1 ball-example-2))
(make-two-balls
(move-ball (two-balls-ball1 (make-two-balls ball-example-1 ball-example-2)))
(move-ball (two-balls-ball2 (make-two-balls ball-example-1 ball-example-2))))
(two-balls-ball1 (make-two-balls ball-example-1 ball-example-2))
ball-example-1
(make-two-balls
(move-ball ball-example-1)
(move-ball (two-balls-ball2 (make-two-balls ball-example-1 ball-example-2))))
(two-balls-ball2 (make-two-balls ball-example-1 ball-example-2))
ball-example-2
(make-two-balls
(move-ball ball-example-1)
(move-ball ball-example-2))
|#
; draw-two-balls : Ball -> Image
(define (draw-two-balls tb)
(overlay (draw-ball (two-balls-ball1 tb))
(draw-ball (two-balls-ball2 tb))))
Piazza has clarification on homework
Homework
[[Lecture 8 - Extended Structures]]
(define-struct ball [x y vx vy])
Nested structured data:
(define-struct two-balls [ball1 ball2])
Templates are essentially the reverse of the constructor function (they unpack the box instead of create the box)
Funciton templates should also be nested for simplicity also as a reminder that you need a helper function
(define (two-balls-template tb)
(... (ball-template (two-balls-ball1 tb)) ...
(ball-template (two-balls-ball2 tb)) ...))
Recall the issue with draw-ball that it draws two backgrounds and one completly obstructs the other. This is because the function draw-ball doesn’t compose nicely and so we should change the function.
;; draw-ball : Ball -> Image
;; Draws a ball on given background
(define (draw-ball-on background b)
(place-image (circle 10 "solid" "red") (ball-x b) (ball-y b) background))
We now can have the first ball background image be ball2’s image:
; draw-two-balls : Ball -> Image
(define (draw-two-balls tb)
(draw-ball (two-balls-ball1 tb
(draw-ball (two-balls-ball2 tb))))
Often times small changes break examples so writing expressions instead of literal values in check-expects can prove to be more robust
big-bangcan look for key presses as well (see documentation for a full list of things that big-bangcan do)
on-key - called on any key press
[ ]’s ()’s and {}’s are all handled the same in Racket, but there are conventions
on-key sends both the state of the world and key that was pressed
[on-key handle-key-pressed]
Top down programming is trying programming with ‘placeholders’ and filling in the gaps later. A higher level view of what’s going on
Bottom up programming is building all of the helper functions first. This is useful if you understand everything about a given project
;; flip-two-balls : Two-Balls -> Two-Balls
(define (flip-two-balls tb)
(make-two-balls (flip-ball (two-balls-ball1 tb))
(flip-ball (two-balls-ball2 tb))))
;; handle-key-pressed : Two-Balls String -> Two-Balls
(define (handle-key-pressed tb key)
(cond
[(key=? key "f") (flip-two-balls tb)]
[else tb]))
Yes, big-bang shows an animation, but it returns the same data type as the initial state of the world thus the signature would be:
;; start-game : Two-Balls -> Two-Balls
Recall from
| [[../CS1800 Discrete Structures | CS1800: Discrete Structures]] |
(and #true #true) ; returns true
With the example of (and #false #true) you don’t even need to evaluate the right hand side because it’ll always be false
This is the same with (or #true #false.
Foo and bar are placeholders for text in computer science. Never call a finished product foo or bar
Why is this useful?
; A StringOrNumber is either:
; - string
; - Number
; is-hi? : StringOrNumber -> Boolean
(define (foo x) ; the proper name should be is-hi?
(and (string? x) (string=? x "hi"))
In this case, we can throw any data type at it and it will either return true or false. If it’s not a string, the first expression will be false so there’s no need to check the 2nd expression.
Lecture 9 Code
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Based on code from Lecture 8.
(require 2htdp/image)
(require 2htdp/universe)
;; A Ball is a _(make-ball Real Real Real Real)_.
;;
;; Interpretation: A _(make-ball x y vx vy)_ represents a ball at position
;; (_x_,_y_), moving with velocity (_vx_, _vy_).
(define-struct ball [x y vx vy])
;; A Ball at the origin, moving horizontally.
(define ball-example-1 (make-ball 100 100 5 0))
;; A Ball moving diagonally, going up faster than it is moving right.
(define ball-example-2 (make-ball 25 25 2 3))
;; ball-template : Ball -> ?
(define (ball-template b)
(... (ball-x b) ...
(ball-y b) ...
(ball-vx b) ...
(ball-vy b) ...))
;; move-ball : Ball -> Ball
(define (move-ball b)
(make-ball
(+ (ball-x b) (ball-vx b))
(+ (ball-y b) (ball-vy b))
(ball-vx b)
(ball-vy b)))
;(check-expect (move-ball ball-example-1) (make-ball 110 100 10 0))
(define BACKGROUND (rectangle 200 200 "solid" "grey"))
;; draw-ball : Ball -> Image
;; Draws a ball on _BACKGROUND_.
(define (draw-ball b)
(place-image (circle 10 "solid" "red") (ball-x b) (ball-y b) BACKGROUND))
;; A Two-Balls is a _(make-two-balls Ball Ball)_.
;; Interpretation: A Two-Balls represents two balls moving independently.
(define-struct two-balls [ball1 ball2])
(define ex-tb-1 (make-two-balls (move-ball ball-example-2) ball-example-1))
;; two-balls-template : Two-Balls -> ?
(define (two-balls-template tb)
(... (ball-template (two-balls-ball1 tb)) ...
(ball-template (two-balls-ball2 tb)) ...))
;; move-two-balls : Two-Balls -> Two-Balls
(define (move-two-balls tb)
(make-two-balls
(move-ball (two-balls-ball1 tb))
(move-ball (two-balls-ball2 tb))))
#;(check-expect (move-two-balls (make-two-balls ball-example-1 ball-example-2))
(make-two-balls (move-ball ball-example-1)
(move-ball ball-example-2)))
;; draw-two-balls : Ball -> Image
(define (draw-two-balls tb)
(draw-ball-on (two-balls-ball1 tb)
(draw-ball-on (two-balls-ball2 tb) BACKGROUND)))
;(draw-ball ball-example-1)
;(draw-ball ball-example-2)
;; draw-ball-on : Ball Image -> Image
;; Draws a ball on _BACKGROUND_.
(define (draw-ball-on b background)
(place-image (circle 10 "solid" "red") (ball-x b) (ball-y b) background))
;; flip-ball : Ball -> Ball
(define (flip-ball b)
(make-ball (ball-x b)
(ball-y b)
(* -0.9 (ball-vx b))
(* -0.9 (ball-vy b))))
;; flip-two-balls : Two-Balls -> Two-Balls
(define (flip-two-balls tb)
(make-two-balls (flip-ball (two-balls-ball1 tb))
(flip-ball (two-balls-ball2 tb))))
;; handle-key-pressed : Two-Balls String -> Two-Balls
(define (handle-key-pressed tb key)
(cond
[(key=? key "f") (flip-two-balls tb)]
[else tb]))
;; start-game : Two-Balls -> Two-Balls
(define (start-game init-tb)
(big-bang init-tb
[on-draw draw-two-balls]
[on-tick move-two-balls 0.05]
[on-key handle-key-pressed]))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;(and (and #true #false) (or #false #true))
;; A StringOrNumber is either:
;; - string
;; - number
;; is-hi? : StringOrNumber -> Boolean
(define (is-hi? x)
(and (string? x) (string=? x "hi")))
We are building up to recurrsion
Remeber that office hours are almost all of the time. Recommended to go on Monday
;; Problem: Design a data definition to represent a pie. There are three kinds
;; of pies to consider: pecan pies, cream pies, and fruit pies. For every fruit
;; pie, we need to know its type, and if it is nut-free. For example, an apple
;; pie may contain nuts, whereas a lemon chiffron pie is nut-free.
;; A Pie is one of:
;; - (make-fruit-fill String Boolean)
;; - "pecan"
;; - "cream"
;;
;; Interpretation: "pecan" represents a pecan pie, "cream" represents
;; a cream pie, and (make-fruit-fill type nut-free) represents a
;; fruit pie of type _type_ and _nut-free_ indicates if it is nut free.
Notice the (make-fruit-fill String Boolean) . We don’t need to make another data definition for this because functions should never have to deal with fruit-filled pies in isolation
This data definition is a union (not an enumeration) because there are infinite (make-fruit-fill String Boolean)’s.
(define (pie-template p)
(cond
[(fruit-fill? p) (... (fruit-fill-type p) ...
(fruit-fill-nut-free p) ...)]
[(string=? p "pecan") ...]
[(string=? p "cream") ...]))
Recall Short Circuiting
[[Lecture 9 - Expanding BigBang and Short Circuits]]
You can do the same thing through conditionals as well.
(define (pie->filling/v2 p)
(cond
[(fruit-fill? p) (fruit-fill-type p)]
[(string=? p "pecan") "pecan"]
[(string=? p "cream") "cream"]))
If it gets the 2nd condition, we know it’s not a fruit-fill therefore we knew that it’s a string.
We can also do this:
;; Design a function called pie->filling that produces a string
;; describing the filling.
;; pie->filling : Pie -> String
(define (pie->filling p)
(cond
[(and (string? p) (string=? p "pecan")) "pecan"]
[(and (string? p) (string=? p "cream")) "cream"]
[(fruit-fill? p) (fruit-fill-type p)]))
This example is more robust because you can reorder things and it’s more readable to humans.
If you have an if that returns #true or #false, you can make it more compact by just writing the condition (if it’s the inverse, add (not to the beginning).
Example:
;; requires-baking? : Pie -> Boolean
(define (requires-baking? p)
(cond
[(fruit-fill? p)
;(... (fruit-fill-type p) ...
; (fruit-fill-nut-free p) ...)
;(if (string=? "lemon chiffron" (fruit-fill-type p))
; #false
; #true)
(not (string=? "lemon chiffron" (fruit-fill-type p)))]
[(string=? p "pecan") #true]
[(string=? p "cream") #false]))
Full Pie Example Code
;; Problem: Design a data definition to represent a pie. There are three kinds
;; of pies to consider: pecan pies, cream pies, and fruit pies. For every fruit
;; pie, we need to know its type, and if it is nut-free. For example, an apple
;; pie may contain nuts, whereas a lemon chiffron pie is nut-free.
;; A Pie is one of:
;; - (make-fruit-fill String Boolean)
;; - "pecan"
;; - "cream"
;;
;; Interpretation: "pecan" represents a pecan pie, "cream" represents
;; a cream pie, and (make-fruit-fill type nut-free) represents a
;; fruit pie of type _type_ and _nut-free_ indicates if it is nut free.
(define-struct fruit-fill (type nut-free))
(define (pie-template p)
(cond
[(fruit-fill? p) (... (fruit-fill-type p) ...
(fruit-fill-nut-free p) ...)]
[(string=? p "pecan") ...]
[(string=? p "cream") ...]))
(define ex-pecan "pecan")
(define ex-cream "cream")
;(define ex-apple-pie "apple pie NO NUTS")
(define ex-apple-pie (make-fruit-fill "apple" #false))
(define ex-lf (make-fruit-fill "lemon chiffron" #true))
;; Design a function called pie->filling that produces a string
;; describing the filling.
;; pie->filling : Pie -> String
(define (pie->filling p)
(cond
[(and (string? p) (string=? p "pecan")) "pecan"]
[(and (string? p) (string=? p "cream")) "cream"]
[(fruit-fill? p) (fruit-fill-type p)]))
(define (pie->filling/v2 p)
(cond
[(fruit-fill? p) (fruit-fill-type p)]
[(string=? p "pecan") "pecan"]
[(string=? p "cream") "cream"]))
(check-expect (pie->filling ex-pecan) "pecan")
(check-expect (pie->filling ex-apple-pie) "apple")
;; Design a function called requires->baking? To check if a PIe requires
;; baking. Pecan pies, and all fruit pies, but not the lemon chiffron,
;; require baking.
;; requires-baking? : Pie -> Boolean
(define (requires-baking? p)
(cond
[(fruit-fill? p)
;(... (fruit-fill-type p) ...
; (fruit-fill-nut-free p) ...)
;(if (string=? "lemon chiffron" (fruit-fill-type p))
; #false
; #true)
(not (string=? "lemon chiffron" (fruit-fill-type p)))]
[(string=? p "pecan") #true]
[(string=? p "cream") #false]))
(check-expect (requires-baking? ex-lf) #false)
(check-expect (requires-baking? ex-apple-pie) #true)
Template:
;; A GeoCoord is one of:
;; - Location
;; - PositiveNumber
;; - NegativeNumber
;;
;; Interpretation: It represents either a location on the
;; Earth's surface, an altitude in the air (positive number),
;; or a depth in the sea (negative number).
;; Problem: Complete the data definion for GeoCoord
(define (geocoord-template gc)
(cond
;[(location? gc) (... (location-latitude gc) ...
; (location-longitude gc) ...)]
[(location? gc) (location-template gc)]
[(>= gc 0) ...]
;[(and (number? gc) (>= gc 0)) ???]
[(< gc 0) ...]))
This is also a union.
Full GeoCoord Example Code
;; A Location is a (make-location Number Number).
;;
;; Interpretation: A (make-location lat long) is a coordinate
;; on the Earth's surface.
(define-struct location [latitude longitude])
;; Example Locations
(define boston-location (make-location 42 71))
(define area51-location (make-location 37 115))
(define crater-lake-location (make-location 42 133))
;; location-temp : Location -> ?
(define (location-temp loc)
(... (location-latitude loc) ...
(location-longitude loc) ...))
;; A GeoCoord is one of:
;; - Location
;; - PositiveNumber
;; - NegativeNumber
;;
;; Interpretation: It represents either a location on the
;; Earth's surface, an altitude in the air (positive number),
;; or a depth in the sea (negative number).
;; Problem: Complete the data definion for GeoCoord
(define (geocoord-template gc)
(cond
;[(location? gc) (... (location-latitude gc) ...
; (location-longitude gc) ...)]
[(location? gc) (location-template gc)]
[(>= gc 0) ...]
;[(and (number? gc) (>= gc 0)) ???]
[(< gc 0) ...]))
For HW examples you need at least 3 examples. Make sure you have no Halloween colors!
Structured data and unions are more powerful than we have demonstrated so far.
Example with Employees:
(define-struct fulltime [name salary])
;; A FullTime is a (make-fulltime String Number)
;; Interpretation: A (make-fulltime n s) represents
;; a full time employee named n with annual salary s.
When you write a template, you tell yourself that functions that use the structure should use at least one piece of information from the structure.
;; fulltime-temp : FullTime -> ?
(define (fulltime-template ft)
; Translation: Do something with (fulltime-name ft) and/or
; (fulltime-salary ft)
(... (fulltime-name ft) ... (fulltime-salary ft) ...))
Formal Definitions:
Informal Definitions:
Both fulltime and interns are employees.
See
[[Lecture 10 - Unions and Structures]]
;; An Employee is one of:
;; - FullTime
;; - Intern
;; Interpretation: An Employee of our prestigious company.
If we don’t use a structure directly (for example, FullTime or Intern), we do not need a template for it.
(define (employee-template emp)
(cond
[(fulltime? emp)
; Call a helper function with emp, that consumes
; a Fulltime
(fulltime-template emp)]
; Call a helper function with emp, that consumes an Intern.
[(intern? emp) (intern-template emp)]))
Make a conditional with checks for what structure it is then call different helper functions for each possibility.
Ex: Monthly Pay
;; monthly-pay : Employee -> Number
;; Purpose: Produces the monthly pay for an employee.
(check-expect (monthly-pay employee-1) (* 15 30 4))
(check-expect (monthly-pay employee-2) (/ 75000 12))
(define (monthly-pay emp)
(cond
[(fulltime? emp) (fulltime->monthly-pay emp)]
[(intern? emp) (intern->monthly-pay emp)]))
Unions with multiple structures is very common in the real world
;; An NNN is a non-negative number
In the example of NNN, it is self-explainitory therefore we do not need a data definition for it
You need a template for homework in this calss. If code works but no documentation/template/data definition, you will get about a 30%
; Define the types of data:
; - (make-[structure] ...)
; - (make-[other_structure] ...)
;; An NNN is a non-negative number
; A Species is one of:
; - "dog"
; - "cat"
; - "goldfish"
(define (species-template s)
(cond
[(string=? s "dog") ...]
[(string=? s "cat") ..]
[(string=? s "goldfish") ..]))
(define-struct pet [species age weight])
; A Pet is a (make-pet Species NNN NNN)
; interpretation A (make-pet s a w) represents a pet, where s is the
; species of animal, with age a in human years, and weight w in pounds.
;; TODO: Examples and template
(define ex-goldfish (make-pet "goldfish" 19 (/ 4 16)))
(define ex-goldfish/v2 (make-pet "goldfish" 19 4/16))
(define ex-cat (make-pet "cat" 18 17))
(define ex-dog (make-pet "dog" 6 50))
(define (pet-template p)
; It is a (make-pet ...). Remember to use (pet-species p),
; (pet-age p), and/or (pet-weight p).
(... (pet-species p) ...
(pet-age p) ...
(pet-weight p) ...))
;;-------------------------------------------------------------------
; Design the function pet-years. It consumes a Pet and returns a
; sentence with the pet’s age in the animal’s own years (i.e., dog years,
; cat years or goldfish years). The sentence should be of the form
; "N in animal years" where N is the age in dog years or cat years.
; E.g., for a pet dog of age 10 in human years, pet-years produces
; "70 in animal years".
; One human year is 7 dog years.
; One human year is 4 cat years.
; One human year is 5 goldfish years.
;; Produces a factor to multiply a species age in human years, to get
;; species animal age.
(define (species-to-human-years s)
(cond
[(string=? s "dog") 7]
[(string=? s "Cat") 4]
[(string=? s "goldfish") 5]))
;; pet-years : Pet -> String
(define (pet-years p)
; It is a (make-pet ...). Remember to use (pet-species p),
; (pet-age p), and/or (pet-weight p).
(string-append
(number->string (* (species-to-human-years (pet-species p)) (pet-age p)))
" in animal years"))
Full Lecture Code
;;-----------------------------------------------------------------------------
;; Problem: We have interns, who work at an hourly rate, and
;; full-time employees, who are salaried. We need to keep track
;; of these employees, and print out their paychecks once every
;; month.
(define-struct fulltime [name salary])
;; A FullTime is a (make-fulltime String Number)
;; Interpretation: A (make-fulltime n s) represents
;; a full time employee named n with annual salary s.
(define fulltime-1 (make-fulltime "Josiah Carberry" 75000))
(define fulltime-2 (make-fulltime "Truman Grayson" 61424))
;; fulltime-temp : FullTime -> ?
(define (fulltime-template ft)
; Translation: Do something with (fulltime-name ft) and/or
; (fulltime-salary ft)
(... (fulltime-name ft) ... (fulltime-salary ft) ...))
; (/ hours week)
(define-struct intern [name wage hours/week])
;; An Intern is a (make-intern String Number Number)
;; Interpretation: A (make-intern n w h) represents an intern
;; with name n, hourly wage w, and hours worked per week h.
(define intern-1 (make-intern "Joe" 15 30))
(define (intern-template int)
; Remember to use (intern-name int), (intern-wage int), or
; (intern-hours/week int)
(... (intern-name int) ...
(intern-wage int) ...
(intern-hours/week int) ...))
;; An Employee is one of:
;; - FullTime
;; - Intern
;; Interpretation: An Employee of our prestigious company.
(define employee-1 intern-1)
(define employee-2 fulltime-1)
(define (employee-template emp)
(cond
[(fulltime? emp)
; Call a helper function with emp, that consumes
; a Fulltime
(fulltime-template emp)]
; Call a helper function with emp, that consumes an Intern.
[(intern? emp) (intern-template emp)]))
;;------------------------------------------------------
;; Design the function monthly-pay
;; Assume an intern works exactly 4 weeks per month
;; monthly-pay : Employee -> Number
;; Purpose: Produces the monthly pay for an employee.
(check-expect (monthly-pay employee-1) (* 15 30 4))
(check-expect (monthly-pay employee-2) (/ 75000 12))
(define (monthly-pay emp)
(cond
[(fulltime? emp) (fulltime->monthly-pay emp)]
[(intern? emp) (intern->monthly-pay emp)]))
;; fulltime->monthly-pay : Fulltime -> Number
;; Purpose: Produces the monthly pay of a fulltime employee.
(define (fulltime->monthly-pay ft)
(/ (fulltime-salary ft) 12))
;; intern->monthly-pay : Intern -> Number
(define (intern->monthly-pay int)
(* (intern-wage int) (intern-hours/week int) 4))
;;-------------------------------------------------------------------
;; An NNN is a non-negative number
; A Species is one of:
; - "dog"
; - "cat"
; - "goldfish"
(define (species-template s)
(cond
[(string=? s "dog") ...]
[(string=? s "cat") ..]
[(string=? s "goldfish") ..]))
(define-struct pet [species age weight])
; A Pet is a (make-pet Species NNN NNN)
; interpretation A (make-pet s a w) represents a pet, where s is the
; species of animal, with age a in human years, and weight w in pounds.
;; TODO: Examples and template
(define ex-goldfish (make-pet "goldfish" 19 (/ 4 16)))
(define ex-goldfish/v2 (make-pet "goldfish" 19 4/16))
(define ex-cat (make-pet "cat" 18 17))
(define ex-dog (make-pet "dog" 6 50))
(define (pet-template p)
; It is a (make-pet ...). Remember to use (pet-species p),
; (pet-age p), and/or (pet-weight p).
(... (pet-species p) ...
(pet-age p) ...
(pet-weight p) ...))
;;-------------------------------------------------------------------
; Design the function pet-years. It consumes a Pet and returns a
; sentence with the pet’s age in the animal’s own years (i.e., dog years,
; cat years or goldfish years). The sentence should be of the form
; "N in animal years" where N is the age in dog years or cat years.
; E.g., for a pet dog of age 10 in human years, pet-years produces
; "70 in animal years".
; One human year is 7 dog years.
; One human year is 4 cat years.
; One human year is 5 goldfish years.
;; Produces a factor to multiply a species age in human years, to get
;; species animal age.
(define (species-to-human-years s)
(cond
[(string=? s "dog") 7]
[(string=? s "Cat") 4]
[(string=? s "goldfish") 5]))
;; pet-years : Pet -> String
(define (pet-years p)
; It is a (make-pet ...). Remember to use (pet-species p),
; (pet-age p), and/or (pet-weight p).
(string-append
(number->string (* (species-to-human-years (pet-species p)) (pet-age p)))
" in animal years"))
Saturday 10th - Exam study session (4-6pm)
The lab tomorrow (Oct. 6th) explains how to take an exam
Exam
What if we want a lab with an arbitrary amount of TA’s?
We could do:
(define-struct lab-with-1ta [Name Number])
(define-struct lab-with-2tas [Name Name Number])
(define-struct lab-with-3tas [Name Name Name Number])
This is BAD PRACTICE!
(define-struct lab [section])
(define-struct add-ta [name rest-lab])
;; A FundiesLab is one of:
;; - (make-lab Natural)
;; - (make-add-ta String FundiesLab)
;;
;; Interpretation: A FundiesLab is either a (make-lab n), where n is the section
;; number of the lab (and it has no TAs assigned); or a (make-add-ta name l),
;; name is the name of a TA to add to the lab l.
In the definition of FundiesLab, you use a FundiesLab itself
In this method, you can have arbitrary number of TA’s
You can also “add” TA’s to any already defined lab
How can we unpack the box here?
labadd-ta (in which case we need to do more work);; fundies-lab-template : FundiesLab -> ?
(define (fundies-lab-template fl)
(cond
[(lab? fl) (... (lab-section fl) ...)]
[(add-ta? fl) (... (add-ta-name fl) ...
(fundies-lab-template (add-ta-rest-lab fl)) ...)]))
Notice how the function fundies-lab-template is called inside of itself
This is called a RECURSIVE function
Count the number of TA’s in a given lab
;; Problem: Design a function to count the number of TAs in a lab.
;(check-expect (count-tas lab-ex-1) 0)
;(check-expect (count-tas lab-ex-2) 1)
;(check-expect (count-tas lab-ex-3) 2)
;; count-tas : FundiesLab -> Natural
(define (count-tas fl)
(cond
[(lab? fl) 0]
[(add-ta? fl) (+ 1 (count-tas (add-ta-rest-lab fl)))]))
Check if “Daniel Goldstein” is a member of any given lab
;; Design a function to check if "Daniel Goldstein" is a member of
;; a lab.
;; has-daniel? :: FundiesLab -> Boolean
(check-expect (has-daniel? lab-ex-2) #false)
(check-expect (has-daniel? lab-ex-3) #true)
(define (has-daniel?-bad-style fl)
(cond
[(lab? fl) #false]
[(add-ta? fl) (if (string=? "Daniel Goldstein" (add-ta-name fl))
#true
(if (has-daniel?-bad-style (add-ta-rest-lab fl))
#true
#false))]))
(define lab-ex-4 (make-add-ta "Aislin Black"
(make-add-ta "Daniel Goldstein" (make-lab 30))))
(check-expect (has-daniel? lab-ex-4) #true)
(define (has-daniel? fl)
(cond
[(lab? fl) #false]
[(add-ta? fl) (or (string=? "Daniel Goldstein" (add-ta-name fl))
(has-daniel? (add-ta-rest-lab fl)))]))
Create a String of a FundiesLab which describes itself
;; Design a function that consumes a FundiesLab and produces a string
;; describing it.
;(check-expect (describe-lab lab-ex-3) "Lab 20: Aislin Black Daniel Goldstein")
;; describe-lab : FundiesLab -> String
(define (describe-lab fl)
(cond
[(lab? fl) (string-append "Lab " (number->string (lab-section fl)))]
[(add-ta? fl) (string-append
(describe-lab (add-ta-rest-lab fl))
" "
(add-ta-name fl)
)]))
Full Lecture Code
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Suppose we want to keep track of all the TAs in a lab
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; LabWith1TA
(define-struct lab-with-1ta [ta lab])
;; A LabWith1TA is a (make-lab-with-1ta String Natural)
;;
;; Interpretation: A LabWith1TA represents a Fundies 1 lab section with one TA.
(define example-lab-with-1ta (make-lab-with-1ta "Aislin Black" 18))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; LabWith2TAs
(define-struct lab-with-2tas [ta1 ta2 lab])
;; A LabWith2TAs is a (make-lab-with-2tas String String Natural)
;;
;; Interpretation: A LabWith2TAs represents a Fundies 1 lab section with two
;; TAs.
(define example-lab-with-2tas
(make-lab-with-2tas "Nate Yazdani" "Daniel Goldstein" 13))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; LabWith3TAs
(define-struct lab-with-3tas [ta1 ta2 lab])
;; A LabWith3TAs is a (make-lab-with-3tas String String String Natural)
;;
;; Interpretation: A LabWith3TAs represents a Fundies 1 lab section with three
;; TAs.
;; etc.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define-struct lab [section])
(define-struct add-ta [name rest-lab])
;; A FundiesLab is one of:
;; - (make-lab Natural)
;; - (make-add-ta String FundiesLab)
;;
;; Interpretation: A FundiesLab is either a (make-lab n), where n is the section
;; number of the lab (and it has no TAs assigned); or a (make-add-ta name l),
;; name is the name of a TA to add to the lab l.
(define lab-ex-1 (make-lab 1))
(define lab-ex-2 (make-add-ta "Aislin Black" (make-lab 20)))
(define lab-ex-3 (make-add-ta "Daniel Goldstein" lab-ex-2))
;; fundies-lab-template : FundiesLab -> ?
(define (fundies-lab-template fl)
(cond
[(lab? fl) (... (lab-section fl) ...)]
[(add-ta? fl) (... (add-ta-name fl) ...
(fundies-lab-template (add-ta-rest-lab fl)) ...)]))
;; Problem: Design a function to count the number of TAs in a lab.
;(check-expect (count-tas lab-ex-1) 0)
;(check-expect (count-tas lab-ex-2) 1)
;(check-expect (count-tas lab-ex-3) 2)
;; count-tas : FundiesLab -> Natural
(define (count-tas fl)
(cond
[(lab? fl) 0]
[(add-ta? fl) (+ 1 (count-tas (add-ta-rest-lab fl)))]))
(count-tas lab-ex-3)
;; Design a function to check if "Daniel Goldstein" is a member of
;; a lab.
;; has-daniel? :: FundiesLab -> Boolean
(check-expect (has-daniel? lab-ex-2) #false)
(check-expect (has-daniel? lab-ex-3) #true)
(define (has-daniel?-bad-style fl)
(cond
[(lab? fl) #false]
[(add-ta? fl) (if (string=? "Daniel Goldstein" (add-ta-name fl))
#true
(if (has-daniel?-bad-style (add-ta-rest-lab fl))
#true
#false))]))
(define lab-ex-4 (make-add-ta "Aislin Black"
(make-add-ta "Daniel Goldstein" (make-lab 30))))
(check-expect (has-daniel? lab-ex-4) #true)
(define (has-daniel? fl)
(cond
[(lab? fl) #false]
[(add-ta? fl) (or (string=? "Daniel Goldstein" (add-ta-name fl))
(has-daniel? (add-ta-rest-lab fl)))]))
;; Design a function that consumes a FundiesLab and produces a string
;; describing it.
;(check-expect (describe-lab lab-ex-3) "Lab 20: Aislin Black Daniel Goldstein")
;; describe-lab : FundiesLab -> String
(define (describe-lab fl)
(cond
[(lab? fl) (string-append "Lab " (number->string (lab-section fl)))]
[(add-ta? fl) (string-append
(describe-lab (add-ta-rest-lab fl))
" "
(add-ta-name fl)
)]))
(define-struct ring [color radius more])
;; A Bullseye is a
;; - "center"
;; - (make-ring String NNN Bullseye)
;;
;; Interpretation: Represents concentric rings of a bullseye target, with
;; _"center"_ representing the center (with no rings), and _(make-ring c r b)_
;; representing the target whose outermost ring has color _c_ and radius _r_,
;; and the remaining rings within are _b_.
(define ex-be-1 "center")
(define ex-be-2 (make-ring "red" 10 ex-be-1))
(define ex-be-3 (make-ring "white" 20 ex-be-2))
(define ex-be-4 (make-ring "red" 30 ex-be-3))
(define ex-be-5 (make-ring "green" 35 ex-be-2))
CamelCase for Data Definitions and hypenations for structures
Whenever you have a union, you use a conditional in the template
; bullseye-template : Bullseye -> ?
(define (bullseye-template be)
(cond
[(string? be) ...]
[(ring? be) (... (ring-color be) ...
(ring-radius be) ...
(bullseye-template (ring-more be)) ...)]))
Remeber: whenever you have a box inside another box, you should write a helper function
;; count-rings : Bullseye -> Number
;; Counts the number of rings in a Bullseye; the "center" is not
;; a ring.
(define (count-rings be)
(cond
[(string? be) 0]
[(ring? be) (+ 1 (count-rings (ring-more be)))]))
;; make-bw : Bullseye -> Bullseye
;; Produces a B&W version of the given Bullseye
(define (make-bw be)
(cond
[(string? be) "center"]
[(ring? be) (make-ring
(if (string=? "white" (ring-color be))
"white"
"black")
(ring-radius be)
(make-bw (ring-more be)))]))
For check-expects, you should always check the base case
When writing functions, ask 3 questions:
Nesting dolls
string?, that you onlu have on string in the data definition(define-struct blue-shell (doll))
(define-struct red-shell (doll))
;; A RussianDoll is one of:
;; - "solid"
;; - (make-blue-shell RussianDoll)
;; - (make-red-shell RussianDoll)
;;
;; Interpretation: Represents a collection of russian nesting dolls. _"center"_
;; represents a solid doll. _(make-blue-shell d)_ represents a blue doll that
;; contains _d_ immediately within it. _(make-red-shell d)_ represents a red
;; doll that contains_d_ immediately within it.
;; count-blue : RussianDoll -> Number
(define (count-blue doll)
(cond
[(string? doll) 0]
[(blue-shell? doll)
(+ 1 (count-blue (blue-shell-doll doll)))]
;[(red-shell? doll) 0]
;[(red-shell? doll)
; 0 (count-blue (red-shell-doll doll))]
[(red-shell? doll)
(count-blue (red-shell-doll doll))]))
(define ex-dolls-1 "solid")
(define ex-dolls-2 (make-red-shell ex-dolls-1))
(define ex-dolls-3 (make-blue-shell ex-dolls-2))
(define ex-dolls-4 (make-red-shell ex-dolls-2))
;; russian-doll-template : RussianDoll -> ?
(define (russian-doll-template doll)
(cond
[(string? doll) ...]
[(blue-shell? doll)
(... (russian-doll-template (blue-shell-doll doll)) ...)]
[(red-shell? doll)
(... (russian-doll-template (red-shell-doll doll)) ...)]))
;; Write a function to count the number of blue-painted dolls in a
;; set of russian dolls.
Think of it as a structure with 2 fields
Empty List - '()
ex. (cons 1 (cons 2 (cons 3 '())))
Examples:
(empty? '()) ; true
(cons? (cons 1 '())) ; true
(first ex-list) ; first element
(rest ex-list) ; the rest of the list (2nd element)
Full Lecture Code
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define-struct ring [color radius more])
;; A Bullseye is a
;; - "center"
;; - (make-ring String NNN Bullseye)
;;
;; Interpretation: Represents concentric rings of a bullseye target, with
;; _"center"_ representing the center (with no rings), and _(make-ring c r b)_
;; representing the target whose outermost ring has color _c_ and radius _r_,
;; and the remaining rings within are _b_.
(define ex-be-1 "center")
(define ex-be-2 (make-ring "red" 10 ex-be-1))
(define ex-be-3 (make-ring "white" 20 ex-be-2))
(define ex-be-4 (make-ring "red" 30 ex-be-3))
(define ex-be-5 (make-ring "green" 35 ex-be-2))
;; bullseye-template : Bullseye -> ?
(define (bullseye-template be)
(cond
[(string? be) ...]
[(ring? be) (... (ring-color be) ...
(ring-radius be) ...
(bullseye-template (ring-more be)) ...)]))
;; count-rings : Bullseye -> Number
;; Counts the number of rings in a Bullseye; the "center" is not
;; a ring.
(define (count-rings be)
(cond
[(string? be) 0]
[(ring? be) (+ 1 (count-rings (ring-more be)))]))
;(check-expect (count-rings ex-be-5) 2)
(check-expect (count-rings ex-be-4) 3)
;; make-bw : Bullseye -> Bullseye
;; Produces a B&W version of the given Bullseye
(define (make-bw be)
(cond
[(string? be) "center"]
[(ring? be) (make-ring
(if (string=? "white" (ring-color be))
"white"
"black")
(ring-radius be)
(make-bw (ring-more be)))]))
(check-expect (make-bw ex-be-3)
(make-ring "white" 20 (make-ring "black" 10 "center")))
;;; draw-bullseye : Bullseye -> Bullseye
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define-struct blue-shell (doll))
(define-struct red-shell (doll))
;; A RussianDoll is one of:
;; - "solid"
;; - (make-blue-shell RussianDoll)
;; - (make-red-shell RussianDoll)
;;
;; Interpretation: Represents a collection of russian nesting dolls. _"center"_
;; represents a solid doll. _(make-blue-shell d)_ represents a blue doll that
;; contains _d_ immediately within it. _(make-red-shell d)_ represents a red
;; doll that contains_d_ immediately within it.
;; count-blue : RussianDoll -> Number
(define (count-blue doll)
(cond
[(string? doll) 0]
[(blue-shell? doll)
(+ 1 (count-blue (blue-shell-doll doll)))]
;[(red-shell? doll) 0]
;[(red-shell? doll)
; 0 (count-blue (red-shell-doll doll))]
[(red-shell? doll)
(count-blue (red-shell-doll doll))]))
(define ex-dolls-1 "solid")
(define ex-dolls-2 (make-red-shell ex-dolls-1))
(define ex-dolls-3 (make-blue-shell ex-dolls-2))
(define ex-dolls-4 (make-red-shell ex-dolls-2))
;; russian-doll-template : RussianDoll -> ?
(define (russian-doll-template doll)
(cond
[(string? doll) ...]
[(blue-shell? doll)
(... (russian-doll-template (blue-shell-doll doll)) ...)]
[(red-shell? doll)
(... (russian-doll-template (red-shell-doll doll)) ...)]))
;; Write a function to count the number of blue-painted dolls in a
;; set of russian dolls.
'()(cons 10 '())(first ex-list-1)): returns the first element of the list(rest ex-list-1)): Returns the second element of the list (aka the rest of the list);; A LON (list of numbers) is one of:
;; - '()
;; - (cons Number LON)
;; Interpretation: a list of numbers
(define ex-lon-0 (cons 1 (cons 2 (cons 3 '()))))
(define ex-lon-1 (cons 2 ex-lon-0))
(define (lon-template lon)
(cond
[(empty? lon) ...]
[(cons? lon) (... (first lon) ...
(lon-template (rest lon)) ...)]))
If you return atomic data, you don’t send it through a helper function
LON has to be sent through the helper function (the template);; Write a function sum a list of numbers.
;; sum : LON -> Number
(define (sum lon)
(cond
[(empty? lon) 0]
[(cons? lon) (+ (first lon)
(sum (rest lon)) )]))
;; prod : LON -> Number
(define (prod lon)
(cond
[(empty? lon) 1]
[(cons? lon) (* (first lon)
(prod (rest lon)))]))
You can’t have the product of the empty list when it equals 0. Because the base case is always run, if you multiply it by 0, the entire thing turns to 0. Therefore, the product of empty list is usually 1.
If you want to have the base case 0, you need to do this:
(define (prod/v2 lon)
(cond
[(empty? lon) 0]
[(cons? lon) (* (first lon)
(if (empty? (rest lon))
1
(prod/v2 (rest lon))))]))
Template is exactly the same as lon’s template.
;; A LOS (list of strings) is one of:
;; - '()
;; - (cons String LOS)
;; Interpretation: A list of strings.
(define (los-template los)
(cond
[(empty? los) ...]
[(cons? los) (... (first los) ...
(los-template (rest los)) ...)]))
;; A PosnList is one of:
;; - '()
;; - (cons (make-posn Number Number) PosnList)
(define ex-posn-list-1
(cons (make-posn 137 137)
(cons (make-posn 10 20)
(cons (make-posn 30 40)
'()))))
(define (posn-list-template pl)
(cond
[(empty? pl) ...]
[(cons? pl) (... (posn-x (first pl)) ...
(posn-y (first pl)) ...
(posn-list-template (rest pl)) ...)]))
When writing data definitions, make sure that the base case is first (a matter of style)
Remeber: Don’t ‘unpack’ more than one box with the same template! Send it to another template!
Posn-Structure: (make-posn x y)
;; invert-posnlist :: PosnList -> PosnList
;; Invert all coordinates in the given PosnList
(define (invert-posnlist pl)
(cond
[(empty? pl) '()]
[(cons? pl) (cons (make-posn (* -1 (posn-x (first pl)))
(* -1 (posn-y (first pl))))
(invert-posnlist (rest pl)))]))
Full Lecture Code
;; A LON (list of numbers) is one of:
;; - '()
;; - (cons Number LON)
;; Interpretation: a list of numbers
(define ex-lon-0 (cons 1 (cons 2 (cons 3 '()))))
(define ex-lon-1 (cons 2 ex-lon-0))
(define (lon-template lon)
(cond
[(empty? lon) ...]
[(cons? lon) (... (first lon) ...
(lon-template (rest lon)) ...)]))
;; Write a function sum a list of numbers.
;; sum : LON -> Number
(define (sum lon)
(cond
[(empty? lon) 0]
[(cons? lon) (+ (first lon)
(sum (rest lon)) )]))
;(check-expect (sum ex-lon-0) 6)
;(check-expect (sum ex-lon-1) 8)
;; prod : LON -> Number
(define (prod lon)
(cond
[(empty? lon) 0]
[(cons? lon) (* (first lon)
(prod (rest lon)))]))
;(check-expect (prod (cons 10 (cons 3 (cons 5 '())))) (* 10 3 5))
(prod (cons 10 (cons 3 '())))
#;(define (prod/v2 lon)
(cond
[(empty? lon) 0]
[(cons? lon) (* (first lon)
(if (empty? (rest lon))
1
(prod/v2 (rest lon))))]))
;; A LOS (list of strings) is one of:
;; - '()
;; - (cons String LOS)
;; Interpretation: A list of strings.
(define (los-template los)
(cond
[(empty? los) ...]
[(cons? los) (... (first los) ...
(los-template (rest los)) ...)]))
(define profs
(cons "Amal" (cons "Arjun" (cons "Ben" (cons "John" (cons "Ferd" '()))))))
;; Write a function to calculate the total length of a LOS.
;; count-length : LOS -> Integer
(check-expect (count-length profs)
(+ (string-length "Amal") (string-length "Arjun")
(string-length "Ben") (string-length "John")
(string-length "Ferd")))
(define (count-length los)
(cond
[(empty? los) 0]
[(cons? los) (+ (string-length (first los))
(count-length (rest los)))]))
;; A Coord is a (make-posn Number Number)
(define (coord-template c)
(... (posn-x c) ...
(posn-y c) ...))
#|
;; A PosnList is one of:
;; - '()
;; - (cons Coord PosnList)
(define (posn-list-template/v2 pl)
(cond
[(empty? pl) ...]
[(cons? pl) (... (coord-template (first pl)) ...
(posn-list-template/v2 (rest pl)) ...)]))
|#
;; A PosnList is one of:
;; - '()
;; - (cons (make-posn Number Number) PosnList)
(define ex-posn-list-1
(cons (make-posn 137 137)
(cons (make-posn 10 20)
(cons (make-posn 30 40)
'()))))
(define (posn-list-template pl)
(cond
[(empty? pl) ...]
[(cons? pl) (... (posn-x (first pl)) ...
(posn-y (first pl)) ...
(posn-list-template (rest pl)) ...)]))
;; invert-posnlist :: PosnList -> PosnList
;; Invert all coordinates in the given PosnList
(define (invert-posnlist pl)
(cond
[(empty? pl) '()]
[(cons? pl) (cons (make-posn (* -1 (posn-x (first pl)))
(* -1 (posn-y (first pl))))
(invert-posnlist (rest pl)))]))
(define ex-posn-list-1-negated
(cons (make-posn -137 -137)
(cons (make-posn -10 -20)
(cons (make-posn -30 -40)
'()))))
(check-expect (invert-posnlist ex-posn-list-1) ex-posn-list-1-negated)
Wants feedback for the class
Homework due date pushed back until Saturday
Mid-semester surveys
“Don’t use Reddit; it’s not good for you” - Arjun
Projects will drag on for 3-4 homework assignments
Goal: Build a Big-Bang program
The brainstorm from class:
; X & Y coord of snake's head
; length of snake
; position of snake
; direction in which the snake is moving
; game clock
; food position
;; A Segments is a NEListofPosn
;;
;; Interpretation: The grid coordinates where the snake lies, the
;; position of the head is the first element of the NEList.
(define ex-segs-1 (cons (make-posn 4 4) (cons (make-posn 4 5) '())))
(define ex-segs-2 (cons (make-posn 4 3) ex-segs-1))
(define ex-segs-3 (cons (make-posn 3 3) ex-segs-2))
(define (segs-template ss)
(cond
[(empty? ss) ...]
[(cons? ss) (... (first ss) ...
(segs-template (rest ss)) ...)]))
NEListofPosn = “non-empty list of Posns”
While doing a project, you should switch perspectives (high level vs. low level) frequently
;; A Snake is a (make-snake Direction Segments)
;; Interpretation: A snake _(make-snape d ss)_ is a snake in
;; moving in _d_, and laying at _ss_ on the grid.
(define snake-1 (make-snake "left" ex-segs-1))
(define snake-2 (make-snake "up" ex-segs-2))
(define snake-3 (make-snake "up" ex-segs-3))
(define snake-4 (make-snake "left" ex-segs-3))
(define (snake-template s)
(... (direction-template (snake-dir s)) ...
(segments-template (snake-segs s)) ...))
;; draw-segments : Segments -> Image
(define (draw-segments ss)
(cond
[(empty? ss) BACKGROUND]
[(cons? ss) (place-image SEGMENT-IMAGE
(* 10 (posn-x (first ss)))
(* 10 (posn-y (first ss)))
(draw-segments (rest ss)))]))
;; draw-snake :: Snake -> Image
(define (draw-snake s)
(draw-segments (snake-segs s)))
Full Lecture Code
(require 2htdp/image)
(require 2htdp/universe)
;; Some nice constants
(define BOARD-HEIGHT 20) ; the hieght of the game board in grid squares
(define BOARD-WIDTH 30) ; the width of the gram eboard in grid squares
(define GRID-SQSIZE 10) ; the width and height of the grid squares
(define BOARD-HEIGHT/PIX (* BOARD-HEIGHT GRID-SQSIZE)) ; board height in pixels
(define BOARD-WIDTH/PIX (* BOARD-WIDTH GRID-SQSIZE)) ; board width in pixels
(define BACKGROUND (empty-scene BOARD-WIDTH/PIX BOARD-HEIGHT/PIX))
(define SEGMENT-RADIUS (/ GRID-SQSIZE 2))
(define SEGMENT-IMAGE (circle SEGMENT-RADIUS "solid" "red"))
(define FOOD-RADIUS (floor (* 0.9 SEGMENT-RADIUS)))
(define FOOD-IMAGE (circle FOOD-RADIUS "solid" "green"))
(define TICK-RATE 0.3)
;;;;
;; A Direction is one of:
;; - "left"
;; - "right"
;; - "up"
;; - "down"
(define (direction-template dir)
(cond [(string=? dir "up") ...]
[(string=? dir "down") ...]
[(string=? dir "left") ...]
[(string=? dir "right") ...]))
;; A Segments is one of:
;; - '()
;; - (cons (make-posn PosInt PosInt) Segments)
;;
;; Alternative to above:
;;
;; A Segments is a ListofPosn
;;
;; Correct data definition:
;;
;; A Segments is a NEListofPosn
;;
;; Interpretation: The grid coordinates where the snake lies, the
;; position of the head is the first element of the NEList.
(define ex-segs-1 (cons (make-posn 4 4) (cons (make-posn 4 5) '())))
(define ex-segs-2 (cons (make-posn 4 3) ex-segs-1))
(define ex-segs-3 (cons (make-posn 3 3) ex-segs-2))
(define (segs-template ss)
(cond
[(empty? ss) ...]
[(cons? ss) (... (first ss) ...
(segs-template (rest ss)) ...)]))
(define-struct snake [dir segs])
;; A Snake is a (make-snake Direction Segments)
;; Interpretation: A snake _(make-snape d ss)_ is a snake in
;; moving in _d_, and laying at _ss_ on the grid.
(define snake-1 (make-snake "left" ex-segs-1))
(define snake-2 (make-snake "up" ex-segs-2))
(define snake-3 (make-snake "up" ex-segs-3))
(define snake-4 (make-snake "left" ex-segs-3))
(define (snake-template s)
(... (direction-template (snake-dir s)) ...
(segments-template (snake-segs s)) ...))
;; draw-segments : Segments -> Image
(define (draw-segments ss)
(cond
[(empty? ss) BACKGROUND]
[(cons? ss) (place-image SEGMENT-IMAGE
(* 10 (posn-x (first ss)))
(* 10 (posn-y (first ss)))
(draw-segments (rest ss)))]))
;; draw-snake :: Snake -> Image
(define (draw-snake s)
(draw-segments (snake-segs s)))
; X & Y coord of snake's head
; length of snake
; position of snake
; direction in which the snake is moving
; game clock
; food position
; if a key is pressed
; if-snake is self-intersecting
; X & Y coord of snake's head (in world state)
; length of snake
; position of snake
; dimensions of the board (constant?)
; game clock
; food position
; direction in which the snake is moving
; if a key is pressed
; if-snake is self-intersecting
Midterm grades will be released at the end of the day today
Partner Switch
Beginner Student Language → Intermediate Student Language
(list 1 2 3 4 5)
(list? returns whether or not something is a cons or '()’() can also be written as (list)
Design a function that prefixes every String in a list of Strings with “Hi “
;; Design a function that consumes a ListOfStrings and produces
;; a new list that prefixes all strings with "Hi ".
;; prefix-hi : ListOfStrings -> ListOfStrings
(define (prefix-hi/v1 los)
(cond
[(empty? los) '()]
[(cons? los) (cons (string-append "Hi " (first los))
(prefix-hi/v1 (rest los)))]))
(check-expect (prefix-hi/v1 (list)) (list))
(check-expect (prefix-hi/v1 (list "Arjun" "Amal"))
(list "Hi Arjun" "Hi Amal"))
Design a funciton that prefixes every String in a list of String with “Hi “
;; prefix-bye : ListOfStrings -> ListOfStrings
(define (prefix-bye/v1 los)
(cond
[(empty? los) '()]
[(cons? los) (cons (string-append "Bye " (first los))
(prefix-bye/v1 (rest los)))]))
(check-expect (prefix-bye/v1 (list "Arjun" "Amal"))
(list "Bye Arjun" "Bye Amal"))
Don’t copy and paste code!! Programmers make 1 error for every 10 linues so you would copy and paste the errors as well
The other reason is you’re left with repetitive code
;; prefix-with : String ListOfStrings -> ListOfStrings
(define (prefix-with to-prefix los)
(cond
[(empty? los) '()]
[(cons? los) (cons (string-append to-prefix (first los))
(prefix-with to-prefix (rest los)))]))
;; prefix-hi/v2 : ListOfStrings -> ListOfStrings
(define (prefix-hi/v2 los)
(prefix-with "Hi " los))
;; prefix-bye/v2 : ListOfStrings -> ListOfStrings
(define (prefix-bye/v2 los)
(prefix-with "Bye " los))
(check-expect (prefix-bye/v2 (list "Arjun" "Amal"))
(list "Bye Arjun" "Bye Amal"))
(check-expect (prefix-hi/v2 (list "Arjun" "Amal"))
(list "Hi Arjun" "Hi Amal"))
;; add-ten-all : LON -> LON
(check-expect (add-ten-all '(1 2 3))
'(11 12 13))
(define (add-ten-all lon)
(cond
[(empty? lon) '()]
[(cons? lon) (cons (+ 10 (first lon))
(add-ten-all (rest lon)))]))
;; mul-five-all : LON -> LON
(check-expect (mul-five-all '(1 2 3))
'(5 10 15))
(define (mul-five-all lon)
(cond
[(empty? lon) '()]
[(cons? lon) (cons (* 5 (first lon))
(mul-five-all (rest lon)))]))
There are two fundamental differences between these functions
How can we have only 1 difference?
Create helper function that does the operation on a single number
;; add10 : Number -> Number
(define (add10 n)
(+ 10 n))
;; mul5 : Number -> Number
(define (mul5 n)
(* 5 n))
;; add-ten-all/v2 : LON -> LON
(define (add-ten-all/v2 lon)
(cond
[(empty? lon) '()]
[(cons? lon) (cons (add10 (first lon))
(add-ten-all/v2 (rest lon)))]))
;; mul-five-all/v2 : LON -> LON
(define (mul-five-all/v2 lon)
(cond
[(empty? lon) '()]
[(cons? lon) (cons (mul5 (first lon))
(mul-five-all/v2 (rest lon)))]))
(check-expect (add-ten-all/v2 '(1 2 3))
'(11 12 13))
(check-expect (mul-five-all/v2 '(1 2 3))
'(5 10 15))
;; apply-to-all : (Number -> Number) LON -> LON
;; apply-to-all : (String -> String) LOS -> LOS
(define (apply-to-all f lon)
(cond
[(empty? lon) '()]
[(cons? lon) (cons (f (first lon))
(apply-to-all f (rest lon)))]))
Notice the signature! (The parenthesis note the funciton)
apply-to-all is already built into ISL under the name map
What is the signature of apply-to-all?
;; apply-to-all : (Number -> Number) LON -> LON
;; apply-to-all : (String -> String) LOS -> LOS
Apply-to-all
apply-to-all; apply-to-all : (Number -> Number) LON -> LON
; apply-to-all : (String -> String) LOS -> LOS
But this works with any datatype (not just Number or String). These types of functions are known as “general functions” or “polymorphic functions”
; apply-to-all : {X Y} (X -> Y) [List-of X] -> [List-of Y]
NOTE: The X and Y are in curly brackets to denote that they are arbitrary variables and not previously defined.
many-circlesAlmost always start with the map function
;; many-circles : [List-of Integer] -> [List-of Image]
(define (many-circles l)
(map do-circle l))
“Computers, they’re out to get me. Gotta study my enemies” - Arjun
give-evensapply-to-all (map) because the helper function needs to return something (you can’t ‘skip’ a number);; a.k.a. filter
;; give-kind-of : {X} (X -> Boolean) [List-of X] -> [List-of X]
;; (give-kind-of f (list x1 x2 ... x_n))
;; produces
;; (list ... x_i ... x_j ...) only if (f x_i), (f x_j) is #true
(define (give-kind-of f l)
(cond
[(empty? l) '()]
[(cons? l)
(if (f (first l))
(cons (first l) (give-kind-of f (rest l)))
(give-kind-of f (rest l)))]))
; give-evens : [List-of Number] -> [List-of Number]
(define (give-evens l)
(give-kind-of even? l))
NOTE: give-kind-of is the same as filter
give-capitalizedSimilar to Example 2. You can’t use apply-to-all (map) to it either.
;; capitalized? : String -> Boolean
(define (capitalized? s)
(string=? s (string-upcase s)))
; give-capitalized : [List-of String] -> [List-of String]
(define (give-capitalized l)
(give-kind-of capitalized? l))
Map: always produce a list of the same length
Filter: input [List-of X], always returns [List-of X]
Recall: We derived the built-in functions map and filter
;; apply-to-all : {X Y} (X -> Y) [List-of X] -> [List-of Y]
;;
;; Purpose:
;;
;; _(apply-to-all f (list x y z ...))_ produces the list
;; _(list (f x) (f y) (f z) ...)_.
(define (apply-to-all f l)
(cond
[(empty? l) '()]
[(cons? l) (cons (f (first l))
(apply-to-all f (rest l)))]
Recall that mul5 was the helper function to mul-five-all
This makes it seem like mul5 is an important function outside of mul-five-all (which it’s not)
Local : Can declare a helper function only within another function
many-circles example below);; mul-five-all : LON -> LON
(define (mul-five-all/v2 lon)
(local (;; mul5 : Number -> Number
(define (mul5/v2 n)
(* 5 n)))
(apply-to-all mul5/v2 lon)
These are only necessary when you need to pass more variables into the helper function
many-circles exampleHow can we pass a color into the helper function as well?
Use a local
;; many-circles/v2 : Color [List-of Integer] -> [List-of Image]
(define (many-circles/v2 c l)
(local ((define (do-circle/v2 r)
(circle r "solid" c)))
(apply-to-all do-circle/v2 l)))
mul-all-by exampleMultiply every element in a list by a given number
;; mul-all-by : Number LON -> LON
(define (mul-all-by n lon)
(local ((define (multiplier m)
(* m n)))
(apply-to-all multiplier lon)))
Create an abstraction for sum-all and mul-all (that can be used for things that aren’t just numbers)
There are two differences
;; my-foldr :: { X Y } (X Y -> Y) Y [List-of X] -> Y
(define (my-foldr f base lon)
(cond
[(empty? lon) base]
[(cons? lon) (f (first lon) (my-foldr f base (rest lon)))]))
do-all is already built into Racket as foldr
;; my-foldr :: {X} (X X -> X) X [List-of X] -> X
; THE MOST GENERAL!
;; my-foldr :: {X Y} (X Y -> Y) Y [List-of X] -> Y ; don't have to be the same
total-len;; Problem: Write a function to calculuate the total length of a list of strings
;; total-len-helper : String Number -> Number
(define (total-len-helper x y)
(+ (string-length x) y ))
;; my-foldr :: { X Y } (X Y -> Y) Y [List-of X] -> Y
;; x = String
;; y = Number
(define (total-len los)
(my-foldr ??? 0 los))
(my-foldr cons '() (list 10 20 30 40))
; Returns: (list 10 20 30 40)
Callenge problem:
(define (apply-to-all/v2 f l)
(my-foldr ...))
Full Lecture Code
(require 2htdp/image)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Code adapted from previous lecture
;; mul5 : Number -> Number
(define (mul5 n)
(* 5 n))
(check-expect (mul5 10) 50)
;; apply-to-all : {X Y} (X -> Y) [List-of X] -> [List-of Y]
;;
;; Purpose:
;;
;; _(apply-to-all f (list x y z ...))_ produces the list
;; _(list (f x) (f y) (f z) ...)_.
(define (apply-to-all f l)
(cond
[(empty? l) '()]
[(cons? l) (cons (f (first l))
(apply-to-all f (rest l)))]))
;; mul-five-all : LON -> LON
(define (mul-five-all lon)
(apply-to-all mul5 lon))
(check-expect (mul-five-all (list 1 2 3))
(list 5 10 15))
;; do-circle : Integer -> Image
(define (do-circle r)
(circle r "solid" "red"))
(check-expect (do-circle 5) (circle 5 "solid" "red"))
;; many-circles : [List-of Integer] -> [List-of Image]
(define (many-circles l)
(map do-circle l))
(check-expect (many-circles (list 10 20))
(list (circle 10 "solid" "red")
(circle 20 "solid" "red")))
;; my-filter : {X} (X -> Boolean) [List-of X] -> [List-of X]
;;
;; Purpose:
;;
;; (my-filter f (list x1 x2 ... x_n))
;; produces
;; (list ... x_i ... x_j ...) only if (f x_i), (f x_j) is #true
(define (my-filter f l)
(cond
[(empty? l) '()]
[(cons? l)
(if (f (first l))
(cons (first l) (my-filter f (rest l)))
(my-filter f (rest l)))]))
(define (give-evens l)
(my-filter even? l))
(check-expect (give-evens (list 1 2 3 4 5))
(list 2 4))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; mul-five-all : LON -> LON
(define (mul-five-all/v2 lon)
(local (;; mul5 : Number -> Number
(define (mul5/v2 n)
(* 5 n)))
(apply-to-all mul5/v2 lon)))
; Does not work: (mul5/v2 10)
;; do-circle : Color Integer -> Image
#;(define (apply-to-all f l)
(cond
[(empty? l) '()]
[(cons? l) (cons (f (first l))
(apply-to-all f (rest l)))]))
;; many-circles/v2 : Color [List-of Integer] -> [List-of Image]
(define (many-circles/v2 c l)
(local ((define (do-circle/v2 r)
(circle r "solid" c)))
(apply-to-all do-circle/v2 l)))
#|
Ignore:
(define (silly x)
(local ((define (G)
(+ x x)))
(+ (G 5) x)))
(silly 100)
|#
;; mul-all-by : Number LON -> LON
(define (mul-all-by n lon)
(local ((define (multiplier m)
(* m n)))
(apply-to-all multiplier lon)))
(mul-all-by 100 (list 10 20 30))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; sum-all :: LON -> Number
(define (sum-all lon)
(cond
[(empty? lon) 0]
[(cons? lon) (+ (first lon) (sum-all (rest lon)))]))
;; mul-all :: LON -> Number
(define (mul-all lon)
(cond
[(empty? lon) 1]
[(cons? lon) (* (first lon) (mul-all (rest lon)))]))
;; my-foldr :: (Number Number -> Number) Number LON -> Number
;; my-foldr :: (String String -> String) String LOS -> String
;; my-foldr :: {X} (X X -> X) X [List-of X] -> X
;; my-foldr :: (X Y -> Y) Y [List-of X ] -> Y
;; my-foldr :: { X Y } (X Y -> Y) Y [List-of X] -> Y
(define (my-foldr f base lon)
(cond
[(empty? lon) base]
[(cons? lon) (f (first lon) (my-foldr f base (rest lon)))]))
(define (sum-all/v2 lon)
(my-foldr + 0 lon))
(define (mul-all/v2 lon)
(my-foldr * 1 lon))
(sum-all/v2 (list 10 20 30))
(mul-all/v2 (list 1 2 3 4 5))
(my-foldr beside (rectangle 10 20 "solid" "green") (many-circles (list 10 20 30)))
;; Challenge: Make this work
; (my-foldr beside???? (rectangle 10 20 "solid" "green") (list 10 20 30))
;; Problem: Write a function to calculuate the total length of a list of strings
;; total-len-helper : String Number -> Number
(define (total-len-helper x y)
(+ (string-length x) y ))
;; my-foldr :: { X Y } (X Y -> Y) Y [List-of X] -> Y
;; x = String
;; y = Number
(define (total-len los)
(my-foldr ??? 0 los))
(define (apply-to-all/v2 f l)
(my-foldr ....))
(define (filter/v2 f l)
(my-foldr ....))
“I apologize for swearing. No, not really” - Arjun
; _(map f (list x y x ...))_ producees _(list (f x) (f y) (f z) ...)_.
However, it’s more complicated. It really does this:
; What map really does
(define (add10 x) (+ x 10))
(my-map add10 (cons 1 (cons 2 '())))
(cons (add10 1) (my-map add10 (cons 2 '())))
(cons 11 (my-map add10 (cons 2 '())))
(cons 11 (cons (add10 2) (my-map add10 '())))
(cons 11 (cons 12 (my-map add10 '())))
(cons 11 (cons 12 '()))
(cons (add10 1) (cons (add10 2) '()))
(list (add10 1) (add10 2))
It does not do this:
(list (add10 1) (add10 2))
Although it is close enough for our purposes.
; filter : {X} (X -> Boolean) [List-of X] -> [List-of X]
See previous lectures for more information.
; foldr : {X Y} (X Y -> Y) Y [List-of X] -> Y
Purpose statement:
With 3 elements (x, y, and z):
; Purpose: _(folder f base (list x y z))_ produces _(f x (f y (f z base)))_
With unknown elements:
; Purpose: _(folder f base (list x y ... z))_ produces _(f x (f y (f ... (f z base))))_.
Example
(foldr + 0 (cons 10 (cons 20 (cons 30 '()))))
(+ 10 (+ 20 (+ 30 0)))
; A [List-of X] is one of:
; - '()
; - (cons X [List-of X])
;
; Interpretation: A list of items, where every item is an X.
(define (my-foldr f base l)
(cond
[(empty? lon) base]
[(cons? lon) (f (first l)
(my-foldr f base (rest l)))]))
Notice how foldr (my-foldr) is the same as the list-template.
list-template can be used with foldr (although sometimes it makes it worse)Example:
length - Calculates the length of a list
; my-length : {X} [List-of X] -> Integer
;; my-length : {X} [List-of X] -> Integer
;; Calculuates the length of the given list.
(define (my-length l)
(cond
[(empty? l) 0]
[(cons? l) (+ 1 ; this does not matter: (first l)
(my-length (rest l)))]))
(define (my-length-helper list-item length-of-the-rest)
(+ 1 length-of-the-rest))
(define (my-length/v2 l)
(foldr my-length-helper 0 l))
Creating length (my-length) using foldr.
foldr gives you all items, so if you don’t need it, don’t use it.Example
Creating filter (my-filter) using foldr.
<SLC - my-filter/v2>
my-filter functionWhile writting the ‘same’ function in homeworks, you can check-expect against other versions. (check-expect (function/v1 x) (function/v2 x))
;; my-filter : {X} (X -> Boolean) [List-of X] -> [List-of X]
;;
;; Purpose: _(my-filter f l)_ produces all elements _x_ of _l_ on which
;; _(f x)_ is _#true_.
(define (my-filter/v2 f l)
(cond
[(empty? l) '()]
[(cons? l)
(local ([define the-first (first l)]
[define rest-filtered (my-filter/v2 f (rest l))])
(if (f the-first)
(cons the-first rest-filtered)
rest-filtered))]))
(define (my-filter/v3 f l)
(local ((define (filter-helper the-first rest-filtered)
(if (f the-first)
(cons the-first rest-filtered)
rest-filtered)))
(my-foldr filter-helper '() l)))
(check-expect (my-filter/v2 even? (list 1 2 3 4)) (list 2 4))
(check-expect (my-filter/v3 even? (list 1 2 3 4))
(my-filter/v2 even? (list 1 2 3 4)))
To make the extra argument available to the helper function, you have to make the helper function local.
; Purpose:
; _(build-list f n)_ produces
; _(list (f 0) (f 1) ... (f (- n 1)))_
identity - Produces it’s argument
Build-list produces a list that sends whose elements are the function prodived with the argument 0 through n.
;; countdown : Integer -> String
[define (add-space s)
(string-append s " ")]
;; countdown : Integer -> [List-of Integer]
(define (countdown n)
(local ([define (build-list-helper i)
(- n i)]
)
(foldr string-append
"blastoff!"
(map add-space
(map number->string
(build-list n build-list-helper))))))
;(check-expect (countdown 5) "5 4 3 2 1 blastoff!")
(countdown 5)
Full Lecture Code
(require 2htdp/image)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Code adapted from last week
;; my-map : {X Y} (X -> Y) [List-of X] -> [List-of Y]
;;
;; NOTE: Called this apply-to-all previously
;;
;; Purpose:
;;
;; _(my-map f (list x y z ...))_ produces _(list (f x) (f y) (f z) ...)_.
(define (my-map f l)
(cond
[(empty? l) '()]
[(cons? l) (cons (f (first l))
(my-map f (rest l)))]))
; What map really does
(define (add10 x) (+ x 10))
(my-map add10 (cons 1 (cons 2 '())))
(cons (add10 1) (my-map add10 (cons 2 '())))
(cons 11 (my-map add10 (cons 2 '())))
(cons 11 (cons (add10 2) (my-map add10 '())))
(cons 11 (cons 12 (my-map add10 '())))
(cons 11 (cons 12 '()))
(cons (add10 1) (cons (add10 2) '()))
(list (add10 1) (add10 2))
;; my-filter : {X} (X -> Boolean) [List-of X] -> [List-of X]
;;
;; Purpose: _(my-filter f l)_ produces all elements _x_ of _l_ on which
;; _(f x)_ is _#true_.
(define (my-filter f l)
(cond
[(empty? l) '()]
[(cons? l)
(if (f (first l))
(cons (first l) (my-filter f (rest l)))
(my-filter f (rest l)))]))
;; sum-all :: [List-of Number] -> Number
(define (sum-all lon)
(cond
[(empty? lon) 0]
[(cons? lon) (+ (first lon) (sum-all (rest lon)))]))
;; mul-all :: [List-of Number] -> Number
(define (mul-all lon)
(cond
[(empty? lon) 1]
[(cons? lon) (* (first lon) (mul-all (rest lon)))]))
;; my-foldr :: {X} (X X -> X) X [List-of X] -> X
;;
;; The most general signature:
;;
;; my-foldr :: { X Y } (X Y -> Y) Y [List-of X] -> Y
;;
;; Purpose: _(my-foldr f base (list x y z))_ a.k.a
;; _(my-foldr f base (cons x (cons y (cons z '()))))_ produces:
;; _(f x (f y (f z base)))_
;; Purpose: _(my-foldr f base (list x y z w))_ produces
;; _(f x (f y (f z (f w base)))_
;; Purpose: _(my-foldr f base (list x y ... z))_ produces
;; _(f x (f y (f z (f ... (f z base))))_
(foldr cons '() (list 10 20 30))
(foldr cons '() (cons 10 (cons 20 (cons 30 '()))))
(cons 10 (cons 20 (cons 30 '())))
(foldr + 0 (cons 10 (cons 20 (cons 30 '()))))
(+ 10 (+ 20 (+ 30 0)))
(foldr - 0 (cons 10 (cons 20 (cons 30 '()))))
(- 10 (- 20 (- 30 0)))
(- 30 20 10)
(define (my-foldr f base lon)
(cond
[(empty? lon) base]
[(cons? lon) (f (first lon) (my-foldr f base (rest lon)))]))
(define (mul-all/v2 lon)
(foldr * 1 lon))
(define (sum-all/v2 lon)
(foldr + 0 lon))
;; total-length-helper : String Number -> Number
(define (total-length-helper s n)
(+ (string-length s) n))
;; total-length :: [List-of String] -> Number
(define (total-length los)
(foldr total-length-helper 0 los))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Code from lecture
; A [List-of X] is one of:
; - '()
; - (cons X [List-of X])
;
; Interpretation: A list of items, where every item is an X.
#;(define (my-foldr f base l)
(cond
[(empty? lon) base]
[(cons? lon) (f (first l)
(my-foldr f base (rest l)))]))
;; my-length : {X} [List-of X] -> Integer
;; Calculuates the length of the given list.
(define (my-length l)
(cond
[(empty? l) 0]
[(cons? l) (+ 1 ; this does not matter: (first l)
(my-length (rest l)))]))
(define (my-length-helper list-item length-of-the-rest)
(+ 1 length-of-the-rest))
(define (my-length/v2 l)
(foldr my-length-helper 0 l))
; list-template : [List-of X] -> ?
(define (list-template l)
(cond
[(empty? l) ...]
[(cons? l) (... (first l)
(list-template (rest l)))]))
;; my-filter : {X} (X -> Boolean) [List-of X] -> [List-of X]
;;
;; Purpose: _(my-filter f l)_ produces all elements _x_ of _l_ on which
;; _(f x)_ is _#true_.
(define (my-filter/v2 f l)
(cond
[(empty? l) '()]
[(cons? l)
(local ([define the-first (first l)]
[define rest-filtered (my-filter/v2 f (rest l))])
(if (f the-first)
(cons the-first rest-filtered)
rest-filtered))]))
(define (my-filter/v3 f l)
(local ((define (filter-helper the-first rest-filtered)
(if (f the-first)
(cons the-first rest-filtered)
rest-filtered)))
(my-foldr filter-helper '() l)))
(check-expect (my-filter/v2 even? (list 1 2 3 4)) (list 2 4))
(check-expect (my-filter/v3 even? (list 1 2 3 4))
(my-filter/v2 even? (list 1 2 3 4)))
;; Purpose:
;; _(build-list n f)_ produces
;; _(list (f 0) (f 1) ... (f (- n 1)))_
;; build-list : {X} NonNegativeInteger (Integer -> X) -> [List-of X]
;; countdown : Integer -> String
[define (add-space s)
(string-append s " ")]
;; countdown : Integer -> [List-of Integer]
(define (countdown n)
(local ([define (build-list-helper i)
(- n i)]
)
(foldr string-append
"blastoff!"
(map add-space
(map number->string
(build-list n build-list-helper))))))
;(check-expect (countdown 5) "5 4 3 2 1 blastoff!")
(countdown 5)
“I’ve only fallen asleep while talking once” - Arjun
Things you can do with functions
local;; add-ten : Number -> Number
(define (add-ten n)
(+ n 10))
(map add-ten (list 10 20 30))
Passing add-ten as a parameter
;; add-all-by : Number [List-of Number] -> [List-of Number]
(define (add-all-by n l)
(local (; helper : Number -> Number
[define (helper m)
(+ n m)])
(map helper l)))
;; silly : Any -> (Number -> Number)
(define (silly n)
add-ten)
;; example-number : Number
(define example-number 3487657845)
(define f (silly "dfkjgidsfug"))
;; why : VOID -> Function
;; why : (Number -> Number)
;; why : Number -> Number
(define why add-ten)
We can also functionally re-name functions
;; why : Number -> Number
(define why add-ten)
“Now that I’ve told you how to do that, don’t do that” - Arjun
make-adder;; make-adder : Number -> (Number -> Number)
(define (make-adder m)
(local [; add : Number -> Number
(define (add n)
(+ n m))]
add))
;; add-hundred : Number -> Number
;; add-hundred is add with (= m 100)
(define add-hundred (make-adder 100))
;; add-five is add with (= m 5)
(define add-five (make-adder 5))
(make-adder 7) ; Produces a function: (lambda (al) ...)
; We can also do:
((make-adder 10) 5) ; Produces: 15
guessing-game; guessing-game : Number -> (Number -> String)
(define (guessing-game n)
(local (; guess : Number -> String
[define (guess m)
(cond
[(= m n) "Correct!"]
[(< m n) "Go higher!"]
[(> m n) "Go lower!"])])
guess))
(define game (guessing-game (random 1000000)))
The actual number is hidden from us; the only way to figure it out is to go through the entire guessing game
Recall:
;; add-ten : Number -> Number
(define (add-ten n)
(+ n 10))
We don’t have to give names to functions:
(lambda (n) (+ n 10)) ; A nameless function
Example:
(map (lambda (n) (+ n 10)) (list 10 20 30 40 50 60))
; Returns: (list 20 30 40 50 60 70)
Example:
(filter (lambda (s) (string=? s "hi")) (list "hi" "bye" "hi"))
; Returns: (list "hi" "hi")
“shit” - Arjun
make-adder using lambda:
;; make-adder : Number -> (Number -> Number)
(define (make-adder m)
(lambda (n) (+ m n)))
Full Lecture Code
;; my-map : {X Y} (X -> Y) [List-of X] -> [List-of Y]
(define (my-map f l)
(cond
[(empty? l) '()]
[(cons? l) (cons (f (first l)) (my-map f (rest l)))]))
;; add-all-by : Number [List-of Number] -> [List-of Number]
(define (add-all-by n l)
(local (; helper : Number -> Number
[define (helper m)
(+ n m)])
(map helper l)))
;; silly : Any -> (Number -> Number)
#;(define (silly n)
add-ten)
;; example-number : Number
(define example-number 3487657845)
#;(define f (silly "dfkjgidsfug"))
;; why : VOID -> Function
;; why : (Number -> Number)
;; why : Number -> Number
;(define why add-ten)
;; make-adder : Number -> (Number -> Number)
(define (make-adder m)
(local (;; add : Number -> Number
[define (add n)
(+ m n)])
add ))
;; add-hundred : Number -> Number
;; add-hundred is add with (= m 100)
(define add-hundred (make-adder 100))
;; add-five is add with (= m 5)
(define add-five (make-adder 5))
; guessing-game : Number -> (Number -> String)
(define (guessing-game n)
(local (; guess : Number -> String
[define (guess m)
(cond
[(= m n) "Correct!"]
[(< m n) "Go higher!"]
[(> m n) "Go lower!"])])
guess))
;; add-ten : Number -> Number
(define (add-ten n)
(+ n 10))
(define add-ten/v2 (lambda (n) (+ n 10)))
; (filter (lambda (s) (string=? s "hi")) (list "hi" "bye" "hi"))
;; make-adder : Number -> (Number -> Number)
(define (make-adder m)
(lambda (n) (+ m n)))
;; add-hundred : Number -> Number
;; add-hundred is add with (= m 100)
(define add-hundred (make-adder 100))
; (make-adder 100)
; ====>
; (lambda (n) (+ 100 n))
; (define add-hundred (lambda (n) (+ 100 n)))
(define (add-hundred n) (+ 100 n))
It’s often helpful to require for lists to be non-empty
Examples for when the empty list is meaningless:
;; An [NE-List X] is one of:
;; - (cons X '())
;; - (cons X [NE-List X])
;; Interpretation: A non-empty list of X.
(define (ne-list-template nel)
(cond
[(empty? (rest nel)) (first nel)]
[(not (empty? (rest nel))) (... (first nel) ...
(ne-list-template (rest nel))...)]))
largest;; largest : [NE-List Number] -> Number
(check-expect (largest (list 5 0 0 0 0 4)) 5)
(check-expect (largest (list 4 0 0 0 0 5)) 5)
(check-expect (largest (list 4 0 7 0 0 5)) 7)
(define (largest nel)
(cond
[(empty? (rest nel)) (first nel)]
[(not (empty? (rest nel)))
(if (> (first nel) (largest (rest nel)))
(first nel)
(largest (rest nel)))]))
;; Challenge: rewrite the function above using folder and max
How long does this function take to run?
time - Returns the amount of time it takes for Racket to compute code
Example:
(time (largest (list 1 2 50000000 1 2 3))) ; return essentially 0 (it's so quick)
For the scope of this course, every number takes the same amount of time to compare
For every element, the time doubles for the largest function. So the time would be too much for lists of reasonable length.
We call largest twice (one for the if statement and one that’s returned from the function). To not call it twice, use a local definition.
(define (largest/v2 nel)
(cond
[(empty? (rest nel)) (first nel)]
[(not (empty? (rest nel)))
(local ([define largest-in-rest (largest/v2 (rest nel))])
(if (> (first nel) largest-in-rest)
(first nel)
largest-in-rest))]))
we usually don’t monitor the time it takes to compute something in terms of time (because every computer is different). We, instead, usually figure out how many comparisons it takes.
Short-hand for lambda is just λ.
Recall:
(map (λ (x) (+ x 10)) (list 1 2 3 4))
; Produces (list 11 12 13 14)
(map (λ (name) (string-append "Hi " name)) (list "Arjun" "Amal"))
; Produces (list "Hi Arjun" "Hi Amal")
; NOTE: Because it's a trival example, we can replace _name_ with just _x_.
Example:
;; Problem: design a function that consumes a list of strings and produces
;; those strings of length two in the list
;; only-two-strings : [List-of String] -> [List-of String]
(define (only-two-strings los)
(filter (λ (s) (= (string-length s) 2)) los))
Example:
;; Problem: Design a funciton that consumes a list of strings and determines if
;; they are all strings of length two.
;; all-two-strings? : [List-of String] -> Boolean
(define (all-two-strings? los)
(andmap (λ (s) (= (string-length s) 2)) los))
Example:
;; Design a function that consumes a list of numbers and only produces those
;; numbers that are within a given range.
; nums-in-range : Number Number [List-of Number] -> [List-of Number]
; Purpose: _(nums-in-range lo hi lon)_ produces those numbers in _lon_ that are
; greater than or equal to _lo_ and less than or equal to _hi_.
; [lo, hi].
(define (nums-in-range lo hi lon)
(filter (λ (n) (and (<= lo n) (<= n hi))) lon))
NOTE: You cannot define a helper (non-local) function for this. The lambda calls lo and hi which wouldn’t be available outside the nums-in-range function.
You can also make the ‘helper’ local instead of lambda (exactly the same as if it were lambda).
Full Lecture Code
;; For later
;; mystery : [NE-List Number] -> Number
(define (mystery lon)
(/ (foldr + 0 lon) (foldr (lambda (x n) (+ 1 n)) 0 lon)))
;; A [List-of X] is one of:
;; - '()
;; - (cons X [List-of X])
;; An [NE-List X] is one of:
;; - (cons X '())
;; - (cons X [NE-List X])
;; Interpretation: A non-empty list of X.
;; ex-ne-list-1 : [NE-List Number]
(define ex-ne-list-1 (list 900))
;; ex-ne-list-2 : [NE-List Number]
(define ex-ne-list-2 (list 10 5 11 8))
;; ex-ne-list-3 : [NE-List String]
(define ex-ne-list-3 (list "Fundies" "2500"))
;; TODO(arjun): The template below is not complete.
(define (ne-list-template nel)
(cond
[(empty? (rest nel)) (... (first nel) ...)]
[(not (empty? (rest nel))) (... (first nel) ...
(ne-list-template (rest nel)) ...)]))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; largest : [NE-List Number] -> Number
(define (largest nel)
(cond
[(empty? (rest nel)) (first nel)]
[(not (empty? (rest nel)))
(if (> (first nel) (largest (rest nel)))
(first nel)
(largest (rest nel)))]))
;; Challenge: rewrite the function above using foldr and max
(check-expect (largest (list 5 0 0 0 0 4)) 5)
(check-expect (largest (list 4 0 0 0 0 5)) 5)
(check-expect (largest (list 4 3 0 5 0 2)) 5)
(define (largest/v2 nel)
(cond
[(empty? (rest nel)) (first nel)]
[(not (empty? (rest nel)))
(local ([define largest-in-rest (largest/v2 (rest nel))])
(if (> (first nel) largest-in-rest)
(first nel)
largest-in-rest))]))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Problem: design a function that consumes a list of strings and produces
;; those strings of length two in the list.
;; only-two-strings : [List-of String] -> [List-of String]
(define (only-two-strings los)
(filter (λ (s) (= (string-length s) 2)) los))
(only-two-strings (list "ab" "abc" "d" "de" "def" ""))
;; Problem: Design a function that consumes a list of strings and determines if
;; they are all strings of length two.
;; all-two-strings? : [List-of String] -> Boolean
(define (all-two-strings? los)
(andmap (λ (s) (= (string-length s) 2)) los))
(check-expect (all-two-strings? (list "ab" "cd")) #true)
(check-expect (all-two-strings? (list "ab" "" "cd")) #false)
;; Design a function that consumes a list of numbers and only produces those
;; numbers that are within a given range.
;; nums-in-range : Number Number [List-of Number] -> [List-of Number]
;; Purpose: _(nums-in-range lo hi lon)_ produces those numbers in _lon_ that are
;; greater than or equal to _lo_ and less than or equal to _hi_.
;; [lo, hi].
(define (nums-in-range lo hi lon)
(filter (λ (n) (and (<= lo n) (<= n hi))) lon))
(check-expect (nums-in-range 4 6 (list 4 3 5 10 4 5 6 1))
(list 4 5 4 5 6))
;(define lo 0)
;(define hi 10)
(define (num-in-range lo hi n)
(and (<= lo n) (<= n hi)))
(define (nums-in-range/v2 lo hi lon)
(filter (num-in-range lo hi) lon))
;(nums-in-range/v2 0 10 (list -10 0 5 10 20))
(define (nums-in-range/v3 lo hi lon)
(local ([define (helper n)
(and (<= lo n) (<= n hi))])
(filter helper lon)))
(define (num-in-range/v4 lo hi)
(lambda (n)
(and (<= lo n) (<= n hi))))
(define (nums-in-range/v4 lo hi lon)
(filter (num-in-range/v4 lo hi) lon))
(nums-in-range/v4 0 10 (list -10 0 5 10 20))
No lab quiz tomorrow!
(check-expect (countdown 5) "5 4 3 2 1 Blastoff!")
;; countdown : Number -> String
(define (countdown n)
(foldr
string-append
"Blastoff!"
(build-list n (lambda (i) (string-append (number->string (- n i)) " ")))))
build-list : Takes a number and a function to create a list with the elements from 0 to n with the function applied to them:
(build-list 5 (lambda (n) n))
; Produces (list 0 1 2 3 4 5)
What should you put in a lambda?
(lambda (x) (/ x 0))
; Does not throw an error (you need to call it to get the error)
“Lambdas fuck with your mental model of how things work” - Arjun
(define (func-a x y)
(+ x (* 10 y)))
(func-a 2 300)
; ===>
(+ 2 (* 10 300))
; ===>
(+ 2 3000)
; ===>
3002
“I would hit the step button but everytime I do that, I feel this rage inside me” - Arjun
(define (my-map f l)
(cond
[(empty? l) '()]
[(cons? l) (cons (f (first l)) (my-map f (rest l)))]))
(define (add10 n) (+ n 10))
;(my-map add10 (list 1 2 3))
; ===>
;(cons (add10 (first (list 1 2 3))) (my-map add10 (rest (list 1 2 3))))
; ===>
;(cons (add10 1) (my-map add10 (list 2 3)))
; === ..... ===>
;(cons (add10 1) (cons (add10 2) (cons (add10 3) (my-map add10 '()))))
map, abstractly it turns into the list template (behind the scenes);; make-add-all : Number -> ([List-of Number] -> [List-of Number])
(define (make-add-all n)
(lambda (l)
(map (lambda (i) (+ i n)) l)))
(define add10-all/v2 (make-add-all 10)))
The set of even numbers between even numers between 1 and 10
{2, 4, 6, 8, 10}
{4, 2, 8, 10, 6} (these 2 sets are the same)
Union: {1, 3, 5} U {2, 4, 6} = {1, 2, 3, 4, 5, 6}
Intersection: {1, 3, 5} $\cap$ {3, 5, 7} = {3, 5}
How can we build sets in Racket?
(define ex-set-1 (list 1 3 5))
(define ex-set-2 (list 5 3 1))
; Invalid example: (define ex-set-3 (list 1 1 3 3 5 5))
These are all the same set, but they are different lists
(define ex-set-4 (list "Arjun" "Amal" "Ben"))
;; A [Set X] is a [List-of X]
;; order is irrelevant; no duplicates allowed
;; union : {X} [Set X] [Set X] -> [Set X]
(define (union set1 set2)
(foldr add set2 set1))
(check-expect (union ex-set-1 ex-set-3) (list 1 3 5 2 4 6))
;(check-expect (union
;; intersect : {X} [Set X] [Set X] -> [Set X]
;; add : {X} X [Set X] -> [Set X]
(define (add elem set)
(if (contains? elem set)
set
(cons elem set)))
(check-expect (add 10 ex-set-1) (list 10 1 3 5))
(check-expect (add 3 ex-set-1) ex-set-1)
;; contains? : {X} X [Set X] -> Boolean
(define (contains? elem set)
(ormap (lambda (elem-in-set) (equal? elem-in-set elem)) set))
(check-expect (contains? 5 ex-set-1) #true)
(check-expect (contains? 5 ex-set-2) #true)
(check-expect (contains? 50 ex-set-1) #false)
Using equals? is bad practice
equals? says that {1, 3, 5} and {5, 3, 1} are not the same set (because we are representing the sets as lists where order does matter)Intersect not completed in this lecture.
Full Lecture Code
#|
(check-expect (countdown 5) "5 4 3 2 1 Blastoff!")
;; countdown : Number -> String
(define (countdown n)
(foldr
string-append
"Blastoff!"
(build-list n (lambda (i) (string-append (number->string (- n i)) " ")))))
|#
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
#|
(define (my-function x)
(/ 1 0))
|#
;(lambda (x) (/ x 0))
;((lambda (y) (/ 1 0)) 100)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (func-a x y)
(+ x (* 10 y)))
;(func-a 2 300)
; ===>
;'(+ 2 (* 10 300))
; ===>
;(+ 2 3000)
; ===>
;3002
(define (my-map f l)
(cond
[(empty? l) '()]
[(cons? l) (cons (f (first l)) (my-map f (rest l)))]))
(define (add10 n) (+ n 10))
;(my-map add10 (list 1 2 3))
; ===>
;(cons (add10 (first (list 1 2 3))) (my-map add10 (rest (list 1 2 3))))
; ===>
;(cons (add10 1) (my-map add10 (list 2 3)))
; === ..... ===>
;(cons (add10 1) (cons (add10 2) (cons (add10 3) (my-map add10 '()))))
;;;;;;;;;;;;;;;;;;
;(my-map add10 l)
; ====>
#;(cond
[(empty? l) '()]
[(cons? l) (cons (add10 (first l)) (my-map add10 (rest l)))])
;; add10-all : [List-of Number] -> [List-of Number]
(define (add10-all l)
(cond
[(empty? l) '()]
[(cons? l) (cons (add10 (first l)) (add10-all (rest l)))]))
;;;;;;;;
;; make-add-all : Number -> ([List-of Number] -> [List-of Number])
(define (make-add-all n)
(lambda (l)
(map (lambda (i) (+ i n)) l)))
(define add10-all/v2 (make-add-all 10))
; (define add10-all/v2 (make-add-all 10))
; ===>
; (define add10-all/v2 (lambda (l)
; (map (lambda (i) (+ i 10)) l)))
; ===>
; (define (add10-all/v2 l)
; (map (lambda (i) (+ i 10)) l))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
; { 2, 4, 6, 8, 10 }
; { 4, 2, 8, 10, 6 }
; { 4, 2, 2, 2, 2, 8, 10, 6 }
; { 1, 3, 5 } U { 2, 4, 6 } = { 1, 2, 3, 4, 5, 6}
; { 1, 3, 5 } INTERSECT { 3, 5, 7 } = { 3, 5 }
; {}
(define ex-set-1 (list 1 3 5))
(define ex-set-2 (list 5 3 1))
(define ex-set-3 (list 2 4 6))
; Invalid example: (define ex-set-3 (list 1 1 3 3 3 5))
(define ex-set-4 (list "Arjun" "Amal" "Ben"))
;; A [Set X] is a [List-of X]
;; order is irrelevant; no duplicates allowed
;; (list x y z)
;; (cons x (cons y (cons z '())))
;; (foldr f base (cons x (cons y (cons z '()))))
;; (f x (f y (f z base)))
;; (union (list x y z) set2)
;; (add x (add y (add z set2)))
;; (union '() set2)
;; set2
;; union : {X} [Set X] [Set X] -> [Set X]
(define (union set1 set2)
(foldr add set2 set1))
(check-expect (union ex-set-1 ex-set-3) (list 1 3 5 2 4 6))
;(check-expect (union
;; intersect : {X} [Set X] [Set X] -> [Set X]
;; add : {X} X [Set X] -> [Set X]
(define (add elem set)
(if (contains? elem set)
set
(cons elem set)))
(check-expect (add 10 ex-set-1) (list 10 1 3 5))
(check-expect (add 3 ex-set-1) ex-set-1)
;; contains? : {X} X [Set X] -> Boolean
(define (contains? elem set)
(ormap (lambda (elem-in-set) (equal? elem-in-set elem)) set))
(check-expect (contains? 5 ex-set-1) #true)
(check-expect (contains? 5 ex-set-2) #true)
(check-expect (contains? 50 ex-set-1) #false)
(list ex-set-1)
Recap on Lecture 23 - building sets with lists
Recall:
;; A [Set X] is a [List-of X]
;; order is irrelevant; no duplicates allowed
;; union : {X} [Set X] [Set X] -> [Set X]
(define (union set1 set2)
(foldr add set2 set1))
(check-expect (union ex-set-1 ex-set-3) (list 1 3 5 2 4 6))
;(check-expect (union
;; intersect : {X} [Set X] [Set X] -> [Set X]
;; add : {X} X [Set X] -> [Set X]
(define (add elem set)
(if (contains? elem set)
set
(cons elem set)))
(check-expect (add 10 ex-set-1) (list 10 1 3 5))
(check-expect (add 3 ex-set-1) ex-set-1)
;; contains? : {X} X [Set X] -> Boolean
(define (contains? elem set)
(ormap (lambda (elem-in-set) (equal? elem-in-set elem)) set))
(check-expect (contains? 5 ex-set-1) #true)
(check-expect (contains? 5 ex-set-2) #true)
(check-expect (contains? 50 ex-set-1) #false)
Example:
setA = { 1, 3, 5 }
setB = { 20, 40, 60 }
setA * setB = { (1, 20), (1, 40), (1, 60), (3, 20) … }
“This makes me cringe just a little bit” - Arjun
Function:
;; prod :: [Set X] [Set X] -> [Set (make-pair X Y)]
(define (prod set-a set-b)
(foldr
append
'()
(map
(lambda (a) (map (lambda (b) (make-pair a b)) set-b))
set-a)))
(define ex-set-prod-1 (list 1 3 5 9 10 4))
(define ex-set-prod-2 (list 20 40 60))
(check-expect (length (prod ex-set-prod-1 ex-set-prod-2))
(* (length ex-set-prod-1) (length ex-set-prod-2)))
mapfunctions (for each in the first list, handle each in the second list)Let’s not use lists to represent sets. Instead, let’s use functions
;; Alternate definition:
;; A [Set-of X] = X -> Boolean
;; Interpretation: A set of elements X, represented by their characteristic
;; function.
Example:
(define (ex-fset-1 x)
(or (= x 0)
(= x 10)
(= x 7)))
; This is the same as {0, 7, 10}
(define (ex-fset-2 x)
(or (even? x)
(= x 5)))
; This is the set of all even numbers and 5
Union as a Set:
(define (ex-fset-3 x)
(or (ex-fset-1 x)
(ex-fset-2 x)))
; The union of fset-1 and fset-2
Intersect as a Set:
(define (ex-fset-3 x)
(and (ex-fset-1 x)
(ex-fset-2 x)))
; The union of fset-1 and fset-2
Contains and Add:
;; fcontains : X [Set X] -> Boolean
(define (fcontains? elt set)
(set elt))
;; fadd : {X} X [Set X] -> [Set X]
(define (fadd elem1 set)
(lambda (elem2)
(or (equal? elem2 elem1)
(fcontains? elem2 set))))
fcontains? and not just the set funciton is because the user should not have to think of the set as a function“There’s hopefully a limit to stupid” - Arjun
;; union : {X} [Set X] [Set X] -> [Set X]
(define (funion set1 set2)
(lambda (query-elem)
(or (fcontains? query-elem set1)
(fcontains? query-elem set2))))
(define fset-empty (lambda (query-elem) #false))
(define (fcomplement set)
(lambda (query-elem)
(not (fcontains query-elem set))))
Full Lecture Code
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Adapted from Lecture 23
(define ex-set-1 (list 1 3 5))
(define ex-set-2 (list 5 3 1))
(define ex-set-3 (list 2 4 6))
; Invalid example: (define ex-set-3 (list 1 1 3 3 3 5))
(define ex-set-4 (list "Arjun" "Amal" "Ben"))
;; union : {X} [Set X] [Set X] -> [Set X]
(define (union set1 set2)
(foldr add set2 set1))
(check-expect (union ex-set-1 ex-set-3) (list 1 3 5 2 4 6))
;; Exercise: write intersect
;; add : {X} X [Set X] -> [Set X]
(define (add elem set)
(if (contains? elem set)
set
(cons elem set)))
(check-expect (add 10 ex-set-1) (list 10 1 3 5))
(check-expect (add 3 ex-set-1) ex-set-1)
;; contains? : {X} X [Set X] -> Boolean
(define (contains? elem set)
(ormap (lambda (elem-in-set) (equal? elem-in-set elem)) set))
(check-expect (contains? 5 ex-set-1) #true)
(check-expect (contains? 5 ex-set-2) #true)
(check-expect (contains? 50 ex-set-1) #false)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; setA = { 1, 3, 5 }
; setB = { 20, 40, 60 }
; setA * setB = { (1, 20), (1, 40), (1, 60), (3, 20), (3, 40), (3, 60), (5, 20), (5, 40), (5, 60) }
(define-struct pair [left right])
#;(list
(map (lambda (b) (make-pair (first set-a) b)) set-b)
(map (lambda (b) (make-pair (second set-a) b)) set-b)
(map (lambda (b) (make-pair (third set-a) b)) set-b))
;; prod :: [Set X] [Set X] -> [Set (make-pair X Y)]
(define (prod set-a set-b)
(foldr
append
'()
(map
(lambda (a) (map (lambda (b) (make-pair a b)) set-b))
set-a)))
(define ex-set-prod-1 (list 1 3 5 9 10 4))
(define ex-set-prod-2 (list 20 40 60))
(check-expect (length (prod ex-set-prod-1 ex-set-prod-2))
(* (length ex-set-prod-1) (length ex-set-prod-2)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; "Characteristic function"
(define (ex-fset-1 x)
(or (= x 0)
(= x 10)
(= x 7)))
(define ex-fset-1/v2
(lambda (x)
(or (= x 0)
(= x 10)
(= x 7))))
(define (ex-fset-2 x)
(or (even? x)
(= x 5)))
(define (ex-fset-3 x)
(or (ex-fset-1 x)
(ex-fset-2 x)))
(define (ex-fset-4 x)
(and (ex-fset-1 x)
(ex-fset-2 x)))
;; Alternate definition:
;; A [Set-of X] = X -> Boolean
;; Interpretation: A set of elements X, represented by their characteristic
;; function.
;; fcontains : X [Set X] -> Boolean
(define (fcontains? elt set)
(set elt))
;; fadd : {X} X [Set X] -> [Set X]
(define (fadd elem1 set)
(lambda (elem2)
(or (equal? elem2 elem1)
(fcontains? elem2 set))))
#;(define (ex-fset-1 x)
(or (= x 0)
(= x 10)
(= x 7)))
;((fadd 500 ex-fset-1) 1000)
(define ex-fset-5 (fadd 500 ex-fset-1))
(check-expect (fcontains? 500 ex-fset-5) #true)
(check-expect (fcontains? 0 ex-fset-5) #true)
(check-expect (fcontains? 5000 ex-fset-5) #false)
(define (fadd-nonsense elem1 set)
(lambda (elem2)
(or (equal? elem2 elem1)
(fcontains? elem2 set)
(equal? elem2 78645897243687592))))
;; union : {X} [Set X] [Set X] -> [Set X]
(define (funion set1 set2)
(lambda (query-elem)
(or (fcontains? query-elem set1)
(fcontains? query-elem set2))))
(define fset-empty (lambda (query-elem) #false))
(define fset-avoid-this (lambda (query-elem) #true))
(define (fcomplement set)
(lambda (query-elem)
(not (fcontains query-elem set))))
;; [Set Integer]
;; N is an integer in the range [0, 10]
;; [Set N]
Unions of structs that are self-referential are more powerful than we initially thought.
If we add up the rate of water flow of all the river branches, we get the amount of water flowing in the outlet of the river.
River ends, 10 + 3 + 5 + 11 + 15 = 44
;; A River is one of
;; - (make-stream Number)
;; - (make-merge River River)
(define-struct merge [left right])
(define-struct stream [flow])
(define ex-stream-1 (make-stream 10))
(define ex-stream-2 (make-stream 3))
(define ex-stream-3 (make-stream 5))
(define ex-river-1 (make-merge ex-stream-1 (make-merge ex-stream-2 ex-stream-3)))
(define ex-river-2 (make-merge (make-merge (make-stream 30) (make-stream 20))
(make-stream 40)))
(define ex-river-1-full (make-merge ex-river-1
(make-merge (make-stream 11)
(make-stream 15))))
;; river-template : River -> ?
(define (river-template r)
(cond
[(stream? r) (... (stream-flow r) ...)]
[(merge? r) (... (river-template (merge-left r)) ...
(river-template (merge-right r)) ...)]))
flow-to-ocean;; flow-to-ocean : River -> Number
(check-expect (flow-to-ocean ex-river-1-full) 44)
(check-expect (flow-to-ocean ex-stream-1) 10)
(define (flow-to-ocean r)
(cond
[(stream? r) (stream-flow r)]
[(merge? r) (+ (flow-to-ocean (merge-left r))
(flow-to-ocean (merge-right r)))]))
“There is a limit to the number of things one can keep on his ears at a time” - Arjun
count-streams;; count-streams : River -> Number
;; Purpose: count the total number of streams that feed this big river.
(check-expect (count-streams ex-stream-1) 1)
(check-expect (count-streams ex-river-1-full) 5)
(define (count-streams r)
(cond
[(stream? r) 1]
[(merge? r) (+ (count-streams (merge-left r))
(count-streams (merge-right r)))]))
count-streams and flow-to-ocean“Let’s make this a lamer tree” - Arjun
widest-stream;; widest-stream: River -> Number
;; Purpose: Produces the flow of water through the widest stream that feeds
;; this river.
(check-expect (widest-stream ex-river-1-full) 15)
(define (widest-stream r)
(cond
[(stream? r) (stream-flow r)]
[(merge? r) (max (widest-stream (merge-left r))
(widest-stream (merge-right r)))]))
;; A FruitTree is one of:
;; - (make-fruit Number Boolean)
;; - (make-leaf)
;; - (make-branch FruitTree FruitTree)
(define-struct fruit [weight ripe?])
(define-struct leaf [])
(define-struct branch [left right])
(define ex-tree-1
(make-branch
(make-branch
(make-branch (make-leaf)
(make-leaf))
(make-branch (make-fruit 100 #true)
(make-fruit 10 #false)))
(make-branch (make-leaf)
(make-fruit 50 #true))))
leaf is a structure itself is for two reasons
;; fruit-tree-template : FruitTree -> ?
(define (fruit-tree-template ft)
(cond
[(fruit? ft) (... (fruit-weight ft) ... (fruit-ripe? ft) ...)]
[(leaf? ft) ...]
[(branch? ft) (... (fruit-tree-template (branch-left ft)) ...
(fruit-tree-template (branch-right ft)) ...)]))
Exam on Nov. 23rd.
Error:
(error [STRING]) : Produces Error(define ex-alist-empty '())
;; [AList String]
;; An association list from NUIDs to names.
(define ex-alist-nuids
(list (make-pair 748 "Arjun Guha")
(make-pair 881 "Amal Ahmed")
(make-pair 900 "Benjamin Lerner")))
Lookup Function
;; alookup : Number [AList X] -> X
;; Produces the value associated with _search-key_ in _alist_.
;; *Assumes* that the the key is in _alist_.
(define (alookup search-key alist)
(cond
[(empty? alist) (error "key not found")]
[(cons? alist)
(if (= search-key (pair-key (first alist)))
(pair-value (first alist))
(alookup search-key (rest alist)))]))
(check-error (alookup 0 ex-alist-empty))
(check-expect (alookup 881 ex-alist-nuids) "Amal Ahmed")
(check-expect (alookup 748 ex-alist-nuids) "Arjun Guha
But what if the association list is very long?
Structure things as trees rather than a list.
All of the left nodes have a smaller value and the right nodes have a greater value (kind of sorted)
“Oh, wow. There’s like a phone with a curly thing.” - Arjun
(define-struct leaf [])
(define-struct node [left key value right])
;; A [BST X] is one of:
;; - (make-leaf)
;; - (make-node [BST X] Number X [BST X])
;; Constraint: In _(make-node left key value right)_ all the keys in _left_ are
;; less than _key_ and all the keys in _right_ are greater than _key_.
Every node has a left child and a right child
(define LEAF (make-leaf))
(define ex-bst-0 (make-leaf))
(define ex-bst-1 (make-node LEAF 4 "Daniel" LEAF))
(define ex-bst-2 (make-node LEAF 3 "Amal" ex-bst-1))
(define ex-bst-3
(make-node (make-node
(make-leaf)
7 "Aislin"
(make-leaf))
10 "Ben"
(make-node
(make-node (make-leaf)
15 "Ferd"
(make-leaf))
17 "John"
(make-leaf))))
(define ex-bst-4
(make-node ex-bst-2
5 "Arjun"
ex-bst-3))
How do we know that 5 is on the top?
(define (bst-template abst)
(cond
[(leaf? abst) ...]
[(node? abst) (...
(bst-template (node-left abst) ...)
(node-key abst) ...
(node-value abst) ...
(bst-template (node-right abst) ...))]))
lookup;; lookup : {X} Number [BST X] -> X
(define (lookup query-key abst)
(cond
[(leaf? abst) (error "nobody")]
[(node? abst)
#;(if (= query-key (node-key abst))
(node-value abst)
(if (< query-key (node-key abst))
(lookup query-key (node-left abst))
(lookup query-key (node-right abst))))
(cond
[(= query-key (node-key abst)) (node-value abst)]
[(< query-key (node-key abst)) (lookup query-key (node-left abst))]
;; ; (> query-key (node-key abst))
;; [else (lookup query-key (node-right abst))]
[(> query-key (node-key abst)) (lookup query-key (node-right abst))])]))
(check-expect (lookup 7 ex-bst-4) "Aislin")
(check-error (lookup 8 ex-bst-4))
Try making an insert function
Full Lecture Code
(define-struct pair [key value])
;; An [AList X] is a [List-of (make-pair Number X)]
(define ex-alist-empty '())
;; [AList String]
;; An association list from NUIDs to names.
(define ex-alist-nuids
(list (make-pair 748 "Arjun Guha")
(make-pair 881 "Amal Ahmed")
(make-pair 900 "Benjamin Lerner")))
;; alookup : Number [AList X] -> X
;; Produces the value associated with _search-key_ in _alist_.
;; *Assumes* that the the key is in _alist_.
(define (alookup search-key alist)
(cond
[(empty? alist) (error "key not found")]
[(cons? alist)
(if (= search-key (pair-key (first alist)))
(pair-value (first alist))
(alookup search-key (rest alist)))]))
(check-error (alookup 0 ex-alist-empty))
(check-expect (alookup 881 ex-alist-nuids) "Amal Ahmed")
(check-expect (alookup 748 ex-alist-nuids) "Arjun Guha")
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define-struct leaf [])
(define-struct node [left key value right])
;; A [BST X] is one of:
;; - (make-leaf)
;; - (make-node [BST X] Number X [BST X])
;; Constraint: In _(make-node left key value right)_ all the keys in _left_ are
;; less than _key_ and all the keys in _right_ are greater than _key_.
#;(define (bst-template abst)
(cond
[(leaf? abst) ...]
[(node? abst) (...
(bst-template (node-left abst) ...)
(node-key abst) ...
(node-value abst) ...
(bst-template (node-right abst) ...))]))
(define LEAF (make-leaf))
(define ex-bst-0 (make-leaf))
(define ex-bst-1 (make-node LEAF 4 "Daniel" LEAF))
(define ex-bst-2 (make-node LEAF 3 "Amal" ex-bst-1))
(define ex-bst-3
(make-node (make-node
(make-leaf)
7 "Aislin"
(make-leaf))
10 "Ben"
(make-node
(make-node (make-leaf)
15 "Ferd"
(make-leaf))
17 "John"
(make-leaf))))
(define ex-bst-4
(make-node ex-bst-2
5 "Arjun"
ex-bst-3))
;; lookup : {X} Number [BST X] -> X
(define (lookup query-key abst)
(cond
[(leaf? abst) (error "nobody")]
[(node? abst)
#;(if (= query-key (node-key abst))
(node-value abst)
(if (< query-key (node-key abst))
(lookup query-key (node-left abst))
(lookup query-key (node-right abst))))
(cond
[(= query-key (node-key abst)) (node-value abst)]
[(< query-key (node-key abst)) (lookup query-key (node-left abst))]
;; ; (> query-key (node-key abst))
;; [else (lookup query-key (node-right abst))]
[(> query-key (node-key abst)) (lookup query-key (node-right abst))])]))
(check-expect (lookup 7 ex-bst-4) "Aislin")
(check-error (lookup 8 ex-bst-4))
Exam Monday after next.
Recall Binary Search Trees:
All keys on the right of the nodes have a value higher and all of the keys on the left have a lower value.
You may write signatures for all definitions (not just functions)
(define-struct leaf [])
(define-struct node [left key value right])
;; A [BST X] is one of:
;; - (make-leaf)
;; - (make-node [BST X] Number X [BST X])
;; Constraint: In _(make-node left key value right)_ all the keys in _left_ are
;; less than _key_ and all the keys in _right_ are greater than _key_.
(define (bst-template abst)
(cond
[(leaf? abst) ...]
[(node? abst) (...
(bst-template (node-left abst) ...)
(node-key abst) ...
(node-value abst) ...
(bst-template (node-right abst) ...))]))
;; lookup : {X} Number [BST X] -> X
(define (lookup query-key abst)
(cond
[(leaf? abst) (error "key not found")]
[(node? abst)
(cond
[(= query-key (node-key abst)) (node-value abst)]
[(< query-key (node-key abst)) (lookup query-key (node-left abst))]
[else ; (> query-key (node-key abst))
(lookup query-key (node-right abst))])]))
;; lookup-unordered : {X} Number [BST X] -> X
;; Looks up the key, but does not require the ordering constraint to hold.
(define (lookup-unordered query-key abst)
(cond
[(leaf? abst) (error "key not found")]
[(node? abst)
(cond
[(= query-key (node-key abst)) (node-value abst)]
[else
(if (bst-contains? query-key (node-left abst))
(lookup-unordered query-key (node-left abst))
(lookup-unordered query-key (node-right abst)))])]))
Note: This is the homework problem 11 in homework 9
insert;; insert : {X} Number X [BST X] -> [BST X]
(define (insert query-key new-value abst)
(cond
[(leaf? abst) (make-node LEAF query-key new-value LEAF)]
[(node? abst)
(cond
[(= query-key (node-key abst)) (make-node (node-left abst)
query-key new-value
(node-right abst))]
[(< query-key (node-key abst))
(make-node (insert query-key new-value (node-left abst))
(node-key abst) (node-value abst)
(node-right abst))]
[else ; (> query-key (node-key abst))
(make-node (node-left abst)
(node-key abst) (node-value abst)
(insert query-key new-value (node-right abst)))])]))
“I don’t feel like scrolling. Scrolling is annoying.” - Arjun
“This is evidently my wife’s mask. I’m having trouble with it here.” - Arjun
list->bst“This smells like a foldr.” - Arjun
(define-struct pair (key val))
;; list->bst : {X} [List-of (make-pair Number X)] -> [BST X]
(define (list->bst key-val-list)
; (foldr + 0 lon)
(foldr
(lambda (new-pair partial-bst)
(insert (pair-key new-pair) (pair-val new-pair) partial-bst))
LEAF
key-val-list))
bst-add10 and bst-add100bst-map;; bst-add10 : [BST Number] -> [BST Number]
;; Adds 10 to all numbers in the BST.
;; bst-add100 : [BST Number] -> [BST Number]
;; Adds 100 to all numbers in the BST.
(define (bst-map f abst)
(cond
[(leaf? abst) (make-leaf)]
[(node? abst) (make-node
(bst-map f (node-left abst))
(node-key abst)
(f (node-value abst))
(bst-map f (node-right abst)))]))
Full Lecture Code
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Adapted from Monday's lecture
(define-struct leaf [])
(define-struct node [left key value right])
;; A [BST X] is one of:
;; - (make-leaf)
;; - (make-node [BST X] Number X [BST X])
;; Constraint: In _(make-node left key value right)_ all the keys in _left_ are
;; less than _key_ and all the keys in _right_ are greater than _key_.
#;(define (bst-template abst)
(cond
[(leaf? abst) ...]
[(node? abst) (...
(bst-template (node-left abst) ...)
(node-key abst) ...
(node-value abst) ...
(bst-template (node-right abst) ...))]))
;; LEAF : {X} [BST X]
(define LEAF (make-leaf))
;; ex-bst-1 : [BST String]
(define ex-bst-1 (make-node LEAF 4 "Daniel" LEAF))
;; ex-bst-2 : [BST String]
(define ex-bst-2 (make-node LEAF 3 "Amal" ex-bst-1))
;; ex-bst-3 : [BST String]
(define ex-bst-3
(make-node (make-node LEAF 7 "Aislin" LEAF)
10 "Ben"
(make-node
(make-node LEAF 15 "Ferd" LEAF)
17 "John"
LEAF)))
;; ex-bst-4 : [BST String]
(define ex-bst-4 (make-node ex-bst-2 5 "Arjun" ex-bst-3))
;; ex-bst-5 : [BST Boolean]
(define ex-bst-5 (make-node LEAF 0 #true (make-node LEAF 10 #true LEAF)))
;; lookup : {X} Number [BST X] -> X
(define (lookup query-key abst)
(cond
[(leaf? abst) (error "key not found")]
[(node? abst)
(cond
[(= query-key (node-key abst)) (node-value abst)]
[(< query-key (node-key abst)) (lookup query-key (node-left abst))]
[else ; (> query-key (node-key abst))
(lookup query-key (node-right abst))])]))
(check-expect (lookup 7 ex-bst-4) "Aislin")
(check-error (lookup 8 ex-bst-4))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; bst-contains? : {X} Number [BST X] -> Boolean
(define (bst-contains? query-key abst)
(cond
[(leaf? abst) #false]
[(node? abst) (or
(= query-key (node-key abst))
(bst-contains? query-key (node-left abst))
(bst-contains? query-key (node-right abst)))]))
;; lookup-unordered : {X} Number [BST X] -> X
;; Looks up the key, but does not require the ordering constraint to hold.
(define (lookup-unordered query-key abst)
(cond
[(leaf? abst) (error "key not found")]
[(node? abst)
(cond
[(= query-key (node-key abst)) (node-value abst)]
[else
(if (bst-contains? query-key (node-left abst))
(lookup-unordered query-key (node-left abst))
(lookup-unordered query-key (node-right abst)))])]))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; lookup : {X} Number [BST X] -> X
;; LEAF : {X} [BST X]
;; (define LEAF (make-leaf))
;; insert : {X} Number X [BST X] -> [BST X]
(define (insert query-key new-value abst)
(cond
[(leaf? abst) (make-node LEAF query-key new-value LEAF)]
[(node? abst)
(cond
[(= query-key (node-key abst)) (make-node (node-left abst)
query-key new-value
(node-right abst))]
[(< query-key (node-key abst))
(make-node (insert query-key new-value (node-left abst))
(node-key abst) (node-value abst)
(node-right abst))]
[else ; (> query-key (node-key abst))
(make-node (node-left abst)
(node-key abst) (node-value abst)
(insert query-key new-value (node-right abst)))])]))
(check-expect (lookup -100 (insert -100 "Carter" ex-bst-4)) "Carter")
(check-expect (lookup 17 (insert -100 "Carter" ex-bst-4)) "John")
(define-struct pair (key val))
;; list->bst : {X} [List-of (make-pair Number X)] -> [BST X]
(define (list->bst key-val-list)
; (foldr + 0 lon)
(foldr
(lambda (new-pair partial-bst)
(insert (pair-key new-pair) (pair-val new-pair) partial-bst))
LEAF
key-val-list))
(list->bst (list (make-pair 1 "Arjun") (make-pair 0 "Amal")))
#;(define (bst-template abst)
(cond
[(leaf? abst) ...]
[(node? abst) (...
(bst-template (node-left abst) ...)
(node-key abst) ...
(node-value abst) ...
(bst-template (node-right abst) ...))]))
;; bst-add10 : [BST Number] -> [BST Number]
;; Adds 10 to all numbers in the BST.
;; bst-add100 : [BST Number] -> [BST Number]
;; Adds 100 to all numbers in the BST.
(define (bst-map f abst)
(cond
[(leaf? abst) (make-leaf)]
[(node? abst) (make-node
(bst-map f (node-left abst))
(node-key abst)
(f (node-value abst))
(bst-map f (node-right abst)))]))
Exam on Monday
Exam
First Exam
; An Atom is one of:
; - String
; - Number
; - Boolean
; - Symbol
(define (atom-template a)
(cond
[(string? a) ...]
[(number? a) ...]
[(boolean? a) ...]
[(symbol? a) ...]))
; atom? : Any -> Boolean
(define (atom? a)
(or
(string? a)
(number? a)
(boolean? a)
(symbol? a)))
' at the beginning
(quote ...(symbol? 'foo) ; Returns #true
(symbol=? 'foo 'foo) ; Returns #true
'45 ; Returns the number 45
'"hello" ; Returns the string "hello"
'#true ; Returns the Boolean #true
'"Hello"5 ; Returns the String "Hello" and then the number 5
'(1 2 "hi" #true) ; Returns the list (list 1 2 "hi" #true).
; You can also nest lists by this (but don't nest the quote)
'(1 2 3 4 #true "hello" "again" x y z)
; Returns (list 1 2 3 4 #true "hello" "again" 'x 'y 'z)
'(+ 1 2 3) ; Looks similar to a program that ISL can run.
; This list represents a program
'(define (f x) (+ 2 3 x))
; Returns (list 'define (list 'f 'x) (list '+ 2 3 'x))
; Represents the program : (define (f x) (+ 2 3 x))
; A *symbolic expression* (SExpr) is one of:
; - Atom
; - LOS
(define (sexpr-template sexp)
(cond
[(atom? sexp) (atom-template (sexp)]
[(list? sexp) (los-template sexp)]))
; A *list of SExprs* (LOS) is a [List-of SExpr]
(define (los-template los)
(cond
[(empty? los) ...]
[(cons? los) (... (sexpr-template (first los)) ...
(los-template (rest los)) ...)]))
;; Alternate Defintion:
; A *symbolic expression* (SExpr) is one of:
; - Atom
; - [List-of SExpr]
SExpr are just trees(define ex-sexpr-1 'x)
(define ex-sexpr-2 '(+ 1 2 3))
(define ex-sexpr-2/v2 (list '+ 1 2 3))
(define ex-sexpr-3 '(define (F x) (+ x 10)))
All-Atoms
;; Problem: Write a function to produce a list of all the atoms in an
;; S-expression.
(check-expect (all-atoms ex-sexpr-3) (list 'define 'F 'x '+ 'x 10))
;; all-atoms : SExpr -> [List-of Atom]
(define (all-atoms sexp)
(cond
[(atom? sexp) (list sexp)]
[(list? sexp) (los-all-atoms sexp)]))
;; los-all-atoms : LOS -> [List-of Atom]
(define (los-all-atoms los)
(cond
[(empty? los) '()]
[(cons? los) (append (all-atoms (first los))
(los-all-atoms (rest los)))]))
;; Problem (definitely do this): use list abstractions to solve the problem above
;; Problem: Write a function that concatenates all strings in an S-experssion
;; into a single string.
(define (atom-join-strings a)
(cond
[(string? a) a]
[(number? a) ...]
[(boolean? a) ...]
[(symbol? a) ...]))
(define (join-strings sexp)
(cond
[(atom? sexp) (atom-join-strings sexp)]
[(list? sexp) (los-join-strings sexp)]))
(define (los-join-strings los)
(cond
[(empty? los) ...]
[(cons? los) (... (join-strings (first los)) ...
(los-join-strings (rest los)) ...)]))
Full Lecture Code
; symbol?
;; An Atom is one of:
;; - String
;; - Number
;; - Boolean
;; - Symbol
;; atom? : Any -> Boolean
(define (atom? a)
(or (string? a) (number? a) (boolean? a) (symbol? a)))
;; A *symbolic expression* (SExpr) is one of:
;; - Atom
;; - LOS
;; A *list of SExprs* (LOS) is a [List-of SExpr]
(define (atom-template a)
(cond
[(string? a) ...]
[(number? a) ...]
[(boolean? a) ...]
[(symbol? a) ...]))
(define (sexpr-template sexp)
(cond
[(atom? sexp) (atom-template sexp)]
[(list? sexp) (los-template sexp)]))
(define (los-template los)
(cond
[(empty? los) ...]
[(cons? los) (... (sexpr-template (first los)) ...
(los-template (rest los)) ...)]))
;; Alternative definition:
;; A *symbolic expression* (SExpr) is one of:
;; - Atom
;; - [List-of SExpr]
;; Examples of SExprs
(define ex-sexpr-1 'x)
(define ex-sexpr-2 '(+ 1 2 3))
(define ex-sexpr-2/v2 (list '+ 1 2 3))
(define ex-sexpr-3 '(define (F x) (+ x 10)))
(define ex-sexpr-4 '("+" 1 2 3))
;; Problem: Write a function to produce a list of all the atoms in an
;; S-expression.
(check-expect (all-atoms ex-sexpr-3) (list 'define 'F 'x '+ 'x 10))
;; all-atoms : SExpr -> [List-of Atom]
(define (all-atoms sexp)
(cond
[(atom? sexp) (list sexp)]
[(list? sexp) (los-all-atoms sexp)]))
;; los-all-atoms : LOS -> [List-of Atom]
(define (los-all-atoms los)
(cond
[(empty? los) '()]
[(cons? los) (append (all-atoms (first los))
(los-all-atoms (rest los)))]))
;; Problem (definitely do this): use list abstractions to solve the problem above
;; Problem: Write a function that concatenates all strings in an S-experssion
;; into a single string.
(define (atom-join-strings a)
(cond
[(string? a) a]
[(number? a) ...]
[(boolean? a) ...]
[(symbol? a) ...]))
(define (join-strings sexp)
(cond
[(atom? sexp) (atom-join-strings sexp)]
[(list? sexp) (los-join-strings sexp)]))
(define (los-join-strings los)
(cond
[(empty? los) ...]
[(cons? los) (... (join-strings (first los)) ...
(los-join-strings (rest los)) ...)]))
2 more homework assignments (after this one)
;; A *list of SExprs* (LOS) is a [List-of SExpr]
(define (atom-template a)
(cond
[(string? a) ...]
[(number? a) ...]
[(boolean? a) ...]
[(symbol? a) ...]))
(define (sexpr-template sexp)
(cond
[(atom? sexp) (atom-template sexp)]
[(list? sexp) (los-template sexp)]))
(define (los-template los)
(cond
[(empty? los) ...]
[(cons? los) (... (sexpr-template (first los)) ...
(los-template (rest los)) ...)]))
;; Examples of SExprs
(define ex-sexpr-1 'x)
(define ex-sexpr-2 (list '+ 1 2 3))
(define ex-sexpr-3 (list 'define (list 'F 'x) (list '+ 'x 10)))
(define ex-sexpr-4 (list (list 'x 20) (list 'y 30) (list 'z 40)))
(check-expect (replace-symbol '(x y z 10 20) 'x 500) '(500 y z 10 20))
(check-expect (replace-symbol '(x x) 'x #true) '(#true #true))
(check-expect (replace-symbol '(y z) 'x 50) '(y z))
;; replace-symbol : SExpr Symbol SExpr -> SExpr
(define (replace-symbol sexp symbol new-sexpr)
(cond
[(atom? sexp) (replace-symbol-atom sexp symbol new-sexpr)]
[(list? sexp) (replace-symbol-los sexp symbol new-sexpr)]))
;; replace-symbol-los : LOS Symbol SExpr -> LOS
(define (replace-symbol-los los symbol new-sexpr)
(cond
[(empty? los) '()]
[(cons? los) (cons (replace-symbol (first los) symbol new-sexpr)
(replace-symbol-los (rest los) symbol new-sexpr))]))
;; replace-symbol-atom : Atom Symbol SExpr -> SExpr
(define (replace-symbol-atom a symbol new-sexpr)
(if (and (symbol? a) (symbol=? a symbol))
new-sexpr
a))
(define ex-sexpr-5 '(+ x 10 (* y 20)))
Template:
;; my-append : {X} . [List-of X] [List-of X] -> [List-of X]
(check-expect (my-append '() (list 40 50)) (list 40 50))
(check-expect (my-append (list 40 50) '()) (list 40 50))
(check-expect (my-append (list 10 20 30) (list 40 50)) (list 10 20 30 40 50))
(check-expect (my-append (cons 10 (cons 20 (cons 30 '()))) (list 40 50)) (list 10 20 30 40 50))
(check-expect (cons 10 (my-append (cons 20 (cons 30 '())) (list 40 50))) (list 10 20 30 40 50))
(check-expect (cons 10 (cons 20 (my-append (cons 30 '()) (list 40 50)))) (list 10 20 30 40 50))
(check-expect (cons 10 (cons 20 (cons 30 (my-append '() (list 40 50))))) (list 10 20 30 40 50))
;; add-pairs : [List-of Number] [List-of Number] -> [List-of Number]
;; Constraints: the two lists have the same length.
(define (add-pairs alist blist)
(cond
[(and (empty? alist) (empty? blist)) '()]
[(and (cons? alist) (cons? blist))
(cons (+ (first alist) (first blist))
(add-pairs (rest alist) (rest blist)))]))
(check-expect (add-pairs (list 10 20 30) (list 1 2 3)) (list 11 22 33))
(check-expect (add-pairs '() '()) '())
(define (list=? alist blist)
(cond
[(and (empty? alist) (empty? blist)) #true]
[(and (cons? alist) (cons? blist))
(and (= (first alist) (first blist))
(list=? (rest alist) (rest blist)))]
#;[(and (cons? alist) (cons? blist))
(if (= (length alist) (length blist))
(and (= (first alist) (first blist))
(list=? (rest alist) (rest blist)))
#false)]
[(and (cons? alist) (empty? blist)) #false]
[(and (empty? alist) (cons? blist)) #false]))
Full Lecture Code
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; From last lecture
;; An Atom is one of:
;; - String
;; - Number
;; - Boolean
;; - Symbol
;; atom? : Any -> Boolean
(define (atom? a)
(or (string? a) (number? a) (boolean? a) (symbol? a)))
;; A *symbolic expression* (SExpr) is one of:
;; - Atom
;; - LOS
;; A *list of SExprs* (LOS) is a [List-of SExpr]
(define (atom-template a)
(cond
[(string? a) ...]
[(number? a) ...]
[(boolean? a) ...]
[(symbol? a) ...]))
(define (sexpr-template sexp)
(cond
[(atom? sexp) (atom-template sexp)]
[(list? sexp) (los-template sexp)]))
(define (los-template los)
(cond
[(empty? los) ...]
[(cons? los) (... (sexpr-template (first los)) ...
(los-template (rest los)) ...)]))
;; Examples of SExprs
(define ex-sexpr-1 'x)
(define ex-sexpr-2 (list '+ 1 2 3))
(define ex-sexpr-3 (list 'define (list 'F 'x) (list '+ 'x 10)))
(define ex-sexpr-4 (list (list 'x 20) (list 'y 30) (list 'z 40)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Problem: design a function that replaces all occurences of a symbol in an
;; S-expression with another given S-expression.
(check-expect (replace-symbol '(x y z 10 20) 'x 500) '(500 y z 10 20))
(check-expect (replace-symbol '(x x) 'x #true) '(#true #true))
(check-expect (replace-symbol '(y z) 'x 50) '(y z))
;; replace-symbol : SExpr Symbol SExpr -> SExpr
(define (replace-symbol sexp symbol new-sexpr)
(cond
[(atom? sexp) (replace-symbol-atom sexp symbol new-sexpr)]
[(list? sexp) (replace-symbol-los sexp symbol new-sexpr)]))
;; replace-symbol-los : LOS Symbol SExpr -> LOS
(define (replace-symbol-los los symbol new-sexpr)
(cond
[(empty? los) '()]
[(cons? los) (cons (replace-symbol (first los) symbol new-sexpr)
(replace-symbol-los (rest los) symbol new-sexpr))]))
;; replace-symbol-atom : Atom Symbol SExpr -> SExpr
(define (replace-symbol-atom a symbol new-sexpr)
(if (and (symbol? a) (symbol=? a symbol))
new-sexpr
a))
(define ex-sexpr-5 '(+ x 10 (* y 20)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; my-append : {X} . [List-of X] [List-of X] -> [List-of X]
(check-expect (my-append '() (list 40 50)) (list 40 50))
(check-expect (my-append (list 40 50) '()) (list 40 50))
(check-expect (my-append (list 10 20 30) (list 40 50)) (list 10 20 30 40 50))
(check-expect (my-append (cons 10 (cons 20 (cons 30 '()))) (list 40 50)) (list 10 20 30 40 50))
(check-expect (cons 10 (my-append (cons 20 (cons 30 '())) (list 40 50))) (list 10 20 30 40 50))
(check-expect (cons 10 (cons 20 (my-append (cons 30 '()) (list 40 50)))) (list 10 20 30 40 50))
(check-expect (cons 10 (cons 20 (cons 30 (my-append '() (list 40 50))))) (list 10 20 30 40 50))
;; add-pairs : [List-of Number] [List-of Number] -> [List-of Number]
;; Constraints: the two lists have the same length.
(define (add-pairs alist blist)
(cond
[(and (empty? alist) (empty? blist)) '()]
[(and (cons? alist) (cons? blist))
(cons (+ (first alist) (first blist))
(add-pairs (rest alist) (rest blist)))]))
(check-expect (add-pairs (list 10 20 30) (list 1 2 3)) (list 11 22 33))
(check-expect (add-pairs '() '()) '())
; (check-expect (add-pairs (list 10 20 30) (list 5 1000)) (list 15 1020 1030))
; (check-expect (add-pairs (list 10 20 30) (list 5)) (list 15))
(check-error (add-pairs (list 10 20 30) (list 5)))
#;(define (parallel-template alist blist)
(cond
[(and (empty? alist) (empty? blist)) ...]
[(and (cons? alist) (cons? blist))
(... (first alist) ... (first blist) ...
(parallel-template (rest alist) (rest blist)))]))
;; list=? : {X} . [List-of X] [List-of X] -> Boolean
(check-expect (list=? (list 10 20) (list 10 20)) #true)
(check-expect (list=? (list 10 20) (list 10 20 30)) #false)
(check-expect (list=? '() '()) #true)
(check-expect (list=? (cons 10 '()) '()) #false)
(define (list=? alist blist)
(cond
[(and (empty? alist) (empty? blist)) #true]
[(and (cons? alist) (cons? blist))
(and (= (first alist) (first blist))
(list=? (rest alist) (rest blist)))]
#;[(and (cons? alist) (cons? blist))
(if (= (length alist) (length blist))
(and (= (first alist) (first blist))
(list=? (rest alist) (rest blist)))
#false)]
[(and (cons? alist) (empty? blist)) #false]
[(and (empty? alist) (cons? blist)) #false]))
Recall the templates from Lecture 29.
my-appendblist. As opposed to parallel traversial)(define (my-append alist blist)
(cond
[(empty? alist) blist]
[(cons? alist) (cons (first alist) (my-append (rest alist) blist))]))
But if blist doesn’t change, how can we optimize this so it doesn’t take in blist?
;; my-append : {X} . [List-of X] [List-of X] -> [List-of X]
(define (my-append/v3 alist blist)
(local (;; helper : [List-of X] -> [List-of X]
[define (helper l)
(cond
[(empty? l) blist]
[(cons? l) (cons (first l) (helper (rest l)))])])
(helper alist)))
Challenge: use a list abstraction for the definition of my-append
(define (my-append/v2 l1 l2)
(foldr cons l2 l1))
list-ref - Returns the nth element of a list
(list-ref (list 10 20 30) 0) ; Returns 10
my-list-ref;; my-list-ref : [List-of X] Nat -> X
(define (my-list-ref/v1 alist index)
(if (= index 0)
(first alist)
(my-list-ref/v1 (rest alist) (- index 1))))
What are different ways of writing this function? Can we write this with parallel traversial?
(define (my-list-ref/v2 alist index)
(cond
[(empty? alist) (error "invalid index")]
[(and (cons? alist) (zero? index)) (first alist)]
[(cons? alist) (my-list-ref/v2 (rest alist) (- index 1))]))
list=?Making a more general definition of list=? (because the previous definition only compared numbers)
;; list=? : {X} . (X X -> Boolean) [List-of X] [List-of X] -> Boolean
(define (list=? compare alist blist)
(cond
[(and (empty? alist) (empty? blist)) #true]
[(and (cons? alist) (cons? blist))
(and (compare (first alist) (first blist))
(list=? compare (rest alist) (rest blist)))]
[else #false]))
(define-struct person [name father mother])
;; An FT (family tree) is one of:
;; - 'none
;; - (make-person String FT FT)
;;
;; Interpretation: A family tree is either:
;; - _'none, which indicates that this ancestor is unknown
;; - _(make-person name father mother)_ which represents _name_ on the family
;; tree, with _mother_ as the family tree of _name_'s mother, and _father_
;; as the family tree of their father.
(define ex-qe2-ancestors
(make-person "QE2"
(make-person "George VI" 'none 'none)
(make-person "Elizabeth BL" 'none 'none)))
(define ex-royalty
(make-person "William"
(make-person "Charles"
(make-person "Philip" 'none 'none)
ex-qe2-ancestors)
(make-person "Diana" 'none 'none)))
;; ft=? : FT FT -> Boolean
(define (ft=? ft1 ft2)
(cond
[(and (person? ft1) (person? ft2))
(and (string=? (person-name ft1) (person-name ft2))
(ft=? (person-father ft1) (person-father ft2))
(ft=? (person-mother ft1) (person-mother ft2)))]
[(and (symbol? ft1) (symbol=? ft1 'none)
(symbol? ft2) (symbol=? ft2 'none)) #true]
[else #false]))
;[(and (person? ft1) (symbol? ft2) (symbol=? ft2 'none)) #false]
;[(and (symbol? ft1) (symbol=? ft1 'none) (person? ft2)) #false]))
(check-expect (ft=? ex-royalty ex-royalty) #true)
(check-expect (ft=? ex-royalty ex-qe2-ancestors) #false)
;; An Ancestor is either
;; - "mother"
;; - "father"
;; An AP (Ancestor Path) is a [List-of Ancestor]
;; find-ancestor : FT AP -> String
(define (find-ancestor ft ap)
(cond
[(and (person? ft) (empty? ap)) (person-name ft)]
[(and (person? ft) (cons? ap))
(if (string=? (first ap) "father")
(find-ancestor (person-father ft) (rest ap))
(find-ancestor (person-mother ft) (rest ap)))]
[else (error "dunno")]))
;[(and (symbol=? ft 'none) (empty? ap)) (error "dunno")]
;[(and (symbol=? ft 'none) (cons? ap)) (error "dunno")]))
(check-expect (find-ancestor ex-royalty (list "father" "mother"))
"QE2")
(check-expect (find-ancestor ex-royalty
(list "father" "mother" "mother"))
"Elizabeth BL")
(define-struct node (name following))
;; A Twitter graph is a:
;; [List-of (make-node String [List-of String])]
;; CONSTRAINT: Any follower is an actual node in the graph
(define ex-twitter-1
(list (make-node "A" (list "D" "E"))
(make-node "B" (list "D"))
(make-node "C" (list "A"))
(make-node "D" (list "B"))
(make-node "E" empty)))
Material that is talked about on Monday and Wednesday is not going to be graded so he can talk about anything we want.
Things we are going to talk about next week
Grades will be back by (at least) Friday
One more assignment left
Return the list of sums of numbers up to a certain point in a list
Make a helper function
;; sum-to : [List-of Number] -> [List-of Number]
(define (sum-to lon)
(modified-sum-to 0 lon))
;; sum-so-far is the *accumulator*
(define (modified-sum-to sum-so-far lon)
(cond
[(empty? lon) '()]
[(cons? lon)
(local ([define new-sum-so-far (+ sum-so-far (first lon))])
(cons new-sum-so-far
(modified-sum-to new-sum-so-far (rest lon))))]))
sum-so-far is the accumulator
Challenge: solve-to using list template and no helper function
“If you can work with trees, your life is relatively easy” - Arjun
Edges - Arrows between people
Nodes - The people themselves (or vertices)
Neighbors - Nodes that are immediately adjacent
(define-struct node [name neighbors])
;; A [Graph X] is a [List-of [Node X]]
;; A [Node X] is a (make-node X [List-of X])
;;
;; Interpretation: [Graph X] represents a graph, with nodes labelled X.
;;
;; For each node:
;;
;; 1. _(make-node x (list y-1 ... y-n))_, the graph has the edges from _x_ to
;; _y-1_, ..., and from _x_ to _y-n_.
;;
;; 2. There must be nodes labelled _y-1_, ..., _y-n_ in the graph.
;;
;; Finally, all node labels must be unique.
;; [Graph String]
(define ex-social
(list (make-node "Alice" (list "Bob" "Carol"))
(make-node "Bob" (list "Carol" "David"))
(make-node "Carol" (list "Emma" "David"))
(make-node "David" (list "Frank"))
(make-node "Emma" (list "Alice"))
(make-node "Frank" '())))
This isn’t as easy as trees because a subsection of a graph is not just a part of the bigger tree (think recursion)
This question about getting paths from graphs is very common in computer science
Keep an accumulator of the neighbors that we have already been to
(define-struct person [name mother father])
;; A FamilyTree is a:
;; - (make-person String Person Person)
;; - #false
(define ex-ft (make-person "Alice"
(make-person "Bob" #false #false)
(make-person "Carol"
(make-person "David" #false #false)
#false)))
;; neighbors-of : [Graph String] String -> [List-of String]
(define (neighbors-of g name)
(cond
[(empty? g) (error "not a node")]
[(cons? g) (if (string=? name (node-name (first g)))
(node-neighbors (first g))
(neighbors-of (rest g) name))]))
;; path? : [List-of X] [Graph X] X X -> Boolean
(define (path-helper visited g src dst)
(cond
;[(member? src visited) #false]
[(member? dst (neighbors-of g src)) #true]
[else
(ormap
(lambda (src-neighbor)
(path-helper (cons src visited) g src-neighbor dst))
(neighbors-of g src))]))
;; path? : [Graph X] X X -> Boolean
(define (path? g src dst)
(path-helper '() g src dst))
Full Lecture Code
;; Problem: Design a function that consumes a list of numbers
;; and produces a list of numbers, where each number in the output
;; is the corresponding number in the input, added to all the preceding
;; numbers in the input.
;; sum-to : [List-of Number] -> [List-of Number]
(define (sum-to lon)
(modified-sum-to 0 lon))
;; sum-so-far is the *accumulator*
(define (modified-sum-to sum-so-far lon)
(cond
[(empty? lon) '()]
[(cons? lon)
(local ([define new-sum-so-far (+ sum-so-far (first lon))])
(cons new-sum-so-far
(modified-sum-to new-sum-so-far (rest lon))))]))
;; Challenge: Solve sum-to using list template and *no helper
;; function*.
(check-expect (sum-to '(5 1 6 9)) '(5 6 12 21))
(define-struct node [name neighbors])
;; A [Graph X] is a [List-of [Node X]]
;; A [Node X] is a (make-node X [List-of X])
;;
;; Interpretation: [Graph X] represents a graph, with nodes labelled X.
;;
;; For each node:
;;
;; 1. _(make-node x (list y-1 ... y-n))_, the graph has the edges from _x_ to
;; _y-1_, ..., and from _x_ to _y-n_.
;;
;; 2. There must be nodes labelled _y-1_, ..., _y-n_ in the graph.
;;
;; Finally, all node labels must be unique.
;; [Graph String]
(define ex-social
(list (make-node "Alice" (list "Bob" "Carol"))
(make-node "Bob" (list "Carol" "David"))
(make-node "Carol" (list "Emma" "David"))
(make-node "David" (list "Frank"))
(make-node "Emma" (list "Alice"))
(make-node "Frank" '())))
(define-struct person [name mother father])
;; A FamilyTree is a:
;; - (make-person String Person Person)
;; - #false
(define ex-ft (make-person "Alice"
(make-person "Bob" #false #false)
(make-person "Carol"
(make-person "David" #false #false)
#false)))
;; neighbors-of : [Graph String] String -> [List-of String]
(define (neighbors-of g name)
(cond
[(empty? g) (error "not a node")]
[(cons? g) (if (string=? name (node-name (first g)))
(node-neighbors (first g))
(neighbors-of (rest g) name))]))
;; path? : [List-of X] [Graph X] X X -> Boolean
(define (path-helper visited g src dst)
(cond
;[(member? src visited) #false]
[(member? dst (neighbors-of g src)) #true]
[else
(ormap
(lambda (src-neighbor)
(path-helper (cons src visited) g src-neighbor dst))
(neighbors-of g src))]))
;; path? : [Graph X] X X -> Boolean
(define (path? g src dst)
(path-helper '() g src dst))
Exam will be returned tomorrow morning
NOTE: Graphs are prime Software Engineer interview questions
Problem: design a funciton to reverse a list.
;; Problem: design a function reverse a list.
;; reverse : {X} [List-of X] -> [List-of X]
(define (my-reverse alist)
(cond
[(empty? alist) '()]
[(cons? alist)
(append
(my-reverse (rest alist))
(list (first alist)))]))
;(check-expect (my-reverse (list 10 20 30 40)) (list 40 30 20 10))
(define (my-reverse/v2 alist)
(reverse-helper alist '()))
;(check-expect (my-reverse/v2 (list 10 20 30 40)) (list 40 30 20 10))
;(my-reverse/v2 (list 10 20 30 40))
#|
(reverse-helper (list 10 20 30 40) ???)
..
..
..
(reverse-helper (cons 40 '()) (list 30 20 10))
=> (cons 40 (list 30 20 10))
(reverse-helper '() (list 40 30 20 10))
|#
;; reverse-helper : {X} [List X] [List X] -> [List X]
(define (reverse-helper alist reversed-so-far)
(cond
[(empty? alist) reversed-so-far]
[(cons? alist)
(reverse-helper (rest alist)
; Use (first alist)
(cons (first alist) reversed-so-far))]))
#|
(my-reverse/v2 (list 10 20 30 40))
(rh (cons 10 (cons 20 (cons 30 (cons 40 '())))) '())
(rh (cons 20 (cons 30 (cons 40 '()))) (cons 10 '()))
(rh (cons 30 (cons 40 '())) (cons 20 (cons 10 '())))
|#
(define (my-reverse/v3 alist)
(local ([define (reverse-helper alist reversed-so-far)
(cond
[(empty? alist) reversed-so-far]
[(cons? alist)
(reverse-helper (rest alist)
; Use (first alist)
(cons (first alist) reversed-so-far))])])
(reverse-helper alist '())))
;; my-foldr : {X Y} (X Y -> Y) Y [List-of X] -> Y
(define (my-foldr f base alist)
(cond
[(empty? alist) base]
[(cons? alist) (f (first alist) (my-foldr f base (rest alist)))]))
;; my-foldl : {X Y} (X Y -> Y) Y [List-of X] -> Y
(define (my-foldl f accum alist)
(cond
[(empty? alist) accum]
[(cons? alist)
(my-foldl f (f (first alist) accum) (rest alist))]))
(define (my-reverse/v4 alist)
(my-foldl cons '() alist))
;; (my-foldr f base (cons a (cons b (cons c '()))))
;; => (f a (f b (f c base)))
;; (my-foldl f accum (cons a (cons b (cons c '()))))
;; => (f c (f b (f a accum)))
;; Example:
;; (f c (f b (f a accum))) replace f with cons and accum with '()
;; (cons c (cons b (cons a '())))
Full Lecture Code
(define (my-append alist blist)
(cond
[(empty? alist) blist]
[(cons? alist)
(cons (first alist) (my-append (rest alist) blist))]))
;; Problem: design a function reverse a list.
;; reverse : {X} [List-of X] -> [List-of X]
(define (my-reverse alist)
(cond
[(empty? alist) '()]
[(cons? alist)
(append
(my-reverse (rest alist))
(list (first alist)))]))
;(check-expect (my-reverse (list 10 20 30 40)) (list 40 30 20 10))
(define (my-reverse/v2 alist)
(reverse-helper alist '()))
;(check-expect (my-reverse/v2 (list 10 20 30 40)) (list 40 30 20 10))
;(my-reverse/v2 (list 10 20 30 40))
#|
(reverse-helper (list 10 20 30 40) ???)
..
..
..
(reverse-helper (cons 40 '()) (list 30 20 10))
=> (cons 40 (list 30 20 10))
(reverse-helper '() (list 40 30 20 10))
|#
;; reverse-helper : {X} [List X] [List X] -> [List X]
(define (reverse-helper alist reversed-so-far)
(cond
[(empty? alist) reversed-so-far]
[(cons? alist)
(reverse-helper (rest alist)
; Use (first alist)
(cons (first alist) reversed-so-far))]))
#|
(my-reverse/v2 (list 10 20 30 40))
(rh (cons 10 (cons 20 (cons 30 (cons 40 '())))) '())
(rh (cons 20 (cons 30 (cons 40 '()))) (cons 10 '()))
(rh (cons 30 (cons 40 '())) (cons 20 (cons 10 '())))
|#
(define (my-reverse/v3 alist)
(local ([define (reverse-helper alist reversed-so-far)
(cond
[(empty? alist) reversed-so-far]
[(cons? alist)
(reverse-helper (rest alist)
; Use (first alist)
(cons (first alist) reversed-so-far))])])
(reverse-helper alist '())))
;; my-foldr : {X Y} (X Y -> Y) Y [List-of X] -> Y
(define (my-foldr f base alist)
(cond
[(empty? alist) base]
[(cons? alist) (f (first alist) (my-foldr f base (rest alist)))]))
;; my-foldl : {X Y} (X Y -> Y) Y [List-of X] -> Y
(define (my-foldl f accum alist)
(cond
[(empty? alist) accum]
[(cons? alist)
(my-foldl f (f (first alist) accum) (rest alist))]))
(define (my-reverse/v4 alist)
(my-foldl cons '() alist))
;; (my-foldr f base (cons a (cons b (cons c '()))))
;; => (f a (f b (f c base)))
;; (my-foldl f accum (cons a (cons b (cons c '()))))
;; => (f c (f b (f a accum)))
;; Example:
;; (f c (f b (f a accum))) replace f with cons and accum with '()
;; (cons c (cons b (cons a '())))
(define (f n)
(if (zero? n)
1
(+ 1 (f (- n 1)))))
(define (g n acc)
(if (zero? n)
acc
(g (- n 1) (+ acc 1))))
Exam grades will be released this evening.
Get involved with research and stuff!
(define-struct leaf [])
(define-struct node [left value right])
;; A [BT X] is one of:
;; - (make-leaf)
;; - (make-node BT X BT)
(define ex-bt-1
(make-node (make-node (make-leaf) 10 (make-leaf)) 20 (make-leaf)))
;; flatten-bt : {X} [BT X] -> [List-of X]
(define (flatten-bt abt)
(cond
[(leaf? abt) '()]
[(node? abt) (append (flatten-bt (node-left abt))
(list (node-value abt))
(flatten-bt (node-right abt)))]))
(check-expect (flatten-bt ex-bt-1) '(10 20))
;; flatten-bt-helper : {X} [BT X] [List-of X] -> [List-of X]
(define (flatten-bt-helper abt acc)
(cond
[(leaf? abt) acc]
[(node? abt)
(local ([define new-acc (flatten-bt-helper (node-right abt) acc)])
(flatten-bt-helper (node-left abt)
(cons (node-value abt) new-acc)))]))
;; flatten-bt/v2 : {X} [BT X] -> [List-of X]
(define (flatten-bt/v2 abt)
(flatten-bt-helper abt '()))
apply - Function that takes in a list and uses every element in a list as arguments to the function input
What we should read over break in preperation of Fundies 2
Concluding regular programming today
Then random stuff
< No code posted :( >
Recall new line function (see Lecture 34 for more)
<slc - sort< >
<slc - qsort>
“Bascially all machine learning is recursion problems” - Arjun
<slc - rate of change>
Note: change2 is the limit definition of the derivative
Higher Order Function: Any function that receives another function as an argument
“You are the derivative function” - Arjun
Essentially, can we make a linear function that acts as a line of best fit for a list of points?
“The linear formula is y=mx+b. I’m going to massage this a little bit” - Arjun
Gradient is just a fancy term for slope.
Guess the slope and then guess the y-intercept
(F 5) ⇒ 53
(F 3) ⇒ 33
What is the function?
We need to guess the slope first. If you get lucky and guess 10 and 3 for the slope and y-intercept respectively you get the following:
((linear 5) 10 3) ⇒ 53
((linear 3) 10 3) ⇒ 33
How can we do better than just blind guessing?
How much should you vary between guesses?
(deriv (lambda (slope) (- (F 5) ((linear 5) slope 3))) 7 0.0001) ⇒ ~5.0000
“I’m closing my door because my cat is dying” - Arjun
Recall code from yesterday
Intro to 3D graphing
By using a 3D graph, we can better represent changing both m and b in the function y=m*x+b (recall that we already know x)
(require plot)
(define ex-linear (λ (x) (+ (* 2 x) -2)))
;; linear-at : Num -> (Num Num -> Num)
;; Represents _y = mx + b_. But with two tricks:
;; - _x_, _m_ and _b_ are all parameters
;; - The function first receives _x_ and produces a function that receives _m_ and _b_
(define linear-at
(lambda (x)
(lambda (m b)
(+ (* m x) b))))
;; A plot of the two-argument function:
;;
;; f(x,y) = 2xy + x^2 + 3y
;;
;; Evaluate (plot3d ex-3d-plot)
(define (show-3d-plot-1)
(plot3d (surface3d (λ (x y) (+ (* 2 x y) (* x x) (+ 3 y))) -1 1 -1 1)))
NOTE: You can’t get the derivative of absolute value which is why we square to get the ‘error’
The particular algorithm is called Gradient Descent
NOTE: When actually doing this, we don’t actually build the curve. We use the derivative to move down the slope
; Cannot get to zero error on this example:
; (plot-linear-error '(1 2 3) '(-2 5 -10))
;; High-level idea:
;;
;; 1. Assume we have x-values and y-values (the *training data*)
;; 2. Guess values for m and b (the *parameters* of the model)
;; 3. Calculate the error (the *loss*)
;; 4. Is the loss acceptable? Return the current parameters
;; 5. Pick new values the parameters. Goal is to go "down the slope", i.e., negative of the derivate
;; 6.
We need to derive the function with respect to multiple variables (the example that we’ve used is m and b)
Consider one of the variables to be a constant.
For this example, we are just going to use a numeric derivative (with a small episilon). Essentially, we move slightly in different directions and see how quickly the output changes
;; Partial Derivatives
;; How precise do we want our numeric derivates to me?
(define EPSILON 0.00001)
;; map-index: {X Y} (Nat X -> Y) [List-of X] -> [List-of Y]
;; Similar to map, but also gives the position of the element to _f_.
(define (map/index f alist)
(local (;; map-index/helper : Nat [List-of X] -> [List-of Y]
[define (map/index-helper index alist)
(cond
[(empty? alist) '()]
[else (cons (f index (first alist)) (map/index-helper (+ 1 index) (rest alist)))])])
(map/index-helper 0 alist)))
;; partial-deriv : (Num ... -> Num) [List-of Num] -> [List-of Num]
;; Given an _n_ argument function, and an argument list, calculates its _n_ partial derivates.
(define (partial-derivs F params)
(build-list
(length params) ;; For every parameter to F
(λ (n)
(local (;; Add epsilon to the nth parameter, and leave the others unchanged.
[define params+epsilon
(map/index
(λ (i p) (if (= i n) (+ EPSILON p) p))
params)])
;; We receive a list of parameters for F.
(/ (- (apply F params+epsilon) (apply F params)) EPSILON)))))
“No one know what the fuck the learning rate is” - Arjun
y’all ever just write machine learning in Racket?
Full Lecture Code
#lang racket
(require plot)
(define ex-linear (λ (x) (+ (* 2 x) -2)))
;; linear-at : Num -> (Num Num -> Num)
;; Represents _y = mx + b_. But with two tricks:
;; - _x_, _m_ and _b_ are all parameters
;; - The function first receives _x_ and produces a function that receives _m_ and _b_
(define linear-at
(lambda (x)
(lambda (m b)
(+ (* m x) b))))
;; A plot of the two-argument function:
;;
;; f(x,y) = 2xy + x^2 + 3y
;;
;; Evaluate (plot3d ex-3d-plot)
(define (show-3d-plot-1)
(plot3d (surface3d (λ (x y) (+ (* 2 x y) (* x x) (+ 3 y))) -1 1 -1 1)))
;; A plot of the two-argument function:
;;
;; f(m, b) = m * 2 + b
;;
(define ex-3d-plot-2 (surface3d (λ (m b) (+ (* m 2) b)) -5 5 -5 5))
(define (show-3d-plot-2)
(plot3d ex-3d-plot-2
#:x-label "m axis"
#:y-label "b axis"
#:z-label "y axis"
#:title "Fixed x = 2"))
(define ex-3d-plot-2/v2 (surface3d (linear-at 2) -5 5 -5 5))
;; Notice that the point is on the surface.
(define (show-3d-plot-3)
(plot3d (list ex-3d-plot-2
(points3d (list (list 2 -2 (ex-linear 2))) #:color "red"))
#:x-label "m axis"
#:y-label "b axis"
#:z-label "y axis"
#:title "Fixed x = 2"))
;; What is this function?
(define ex-function-4 (λ (m b) (sqr (- (ex-linear 2) ((linear-at 2) m b)))))
(define ex-3d-plot-4
(surface3d ex-function-4 -5 5 -5 5))
(define (show-3d-plot-4)
(plot3d ex-3d-plot-4
#:x-label "m axis"
#:y-label "b axis"
#:z-label "y axis"
#:title "Fixed x = 2"))
;; Quadratic formula is f(x) = ax^2 + bx + c. Assume c = 0.
(define ex-quadratic (λ (x) (+ (* 2 x x) (* -2 x))))
(define (show-quadratic)
(plot (function ex-quadratic -3 3)))
;; quadratic-at : Num -> (Num Num -> Num)
;; Represents _y = ax^2 + bx_.
(define quadratic-at
(lambda (x)
(lambda (a b)
(+ (* a x x) (* b x)))))
(define (show-quadratic-at-2)
(plot3d
(list
(surface3d (quadratic-at 2) -3 3 -3 3)
(points3d (list (list 2 -2 (ex-quadratic 2)))))
#:x-label "a axis"
#:y-label "b axis"
#:z-label "y axis"
#:title "Fixed x = 2"))
(define ex-quadratic-error (λ (a b) (sqr (- (ex-quadratic 2) ((quadratic-at 2) a b)))))
(define (show-quadratic-error)
(plot3d
(surface3d ex-quadratic-error -3 3 -3 3)
#:x-label "a axis"
#:y-label "b axis"
#:z-label "y axis"
#:title "Fixed x = 2"))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Sum of errors of multiple points
(define (linear-error x-values y-values)
(λ (m b)
(foldr + 0 (map (λ (x y) (sqr (- y ((linear-at x) m b)))) x-values y-values))))
(define (plot-linear-error x-values y-values)
(plot3d
(surface3d (linear-error x-values y-values) -5 5 -5 5)
#:x-label "m axis"
#:y-label "b axis"
#:z-label "y axis"))
(define ex-data-1 '((-0.3993 0.787) (0.425 4.924) (-0.0895 2.6) (0.153 3.545) (-0.4466 0.387) (0.369 4.929) (0.3955 5.35) (-0.338 0.33) (0.1048 3.33) (-0.1397 1.63) (-0.4474 1.002) (-0.2395 2.338) (0.3424 5.48) (-0.1258 2.485) (0.4866 6.24) (-0.1342 2.593) (0.449 4.994) (0.088 2.462) (0.4666 5.70) (0.04956 3.06) (0.4816 5.19) (0.1378 3.393) (-0.2014 2.224) (-0.4887 0.3273) (-0.2225 1.88) (-0.1998 2.72) (-0.0908 1.796) (-0.3513 1.535) (-0.496 0.722) (-0.02463 1.415)))
(define (plot-ex-data-error)
(plot-linear-error (map first ex-data-1) (map second ex-data-1)))
;(plot-linear-error '(1 2 3) '(2 4 6))
; Cannot get to zero error on this example:
; (plot-linear-error '(1 2 3) '(-2 5 -10))
;; High-level idea:
;;
;; 1. Assume we have x-values and y-values (the *training data*)
;; 2. Guess values for m and b (the *parameters* of the model)
;; 3. Calculate the error (the *loss*)
;; 4. Is the loss acceptable? Return the current parameters
;; 5. Pick new values the parameters. Goal is to go "down the slope", i.e., negative of the derivate
;; 6.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Partial Derivatives
;; How precise do we want our numeric derivates to me?
(define EPSILON 0.00001)
;; map-index: {X Y} (Nat X -> Y) [List-of X] -> [List-of Y]
;; Similar to map, but also gives the position of the element to _f_.
(define (map/index f alist)
(local (;; map-index/helper : Nat [List-of X] -> [List-of Y]
[define (map/index-helper index alist)
(cond
[(empty? alist) '()]
[else (cons (f index (first alist)) (map/index-helper (+ 1 index) (rest alist)))])])
(map/index-helper 0 alist)))
;; partial-deriv : (Num ... -> Num) [List-of Num] -> [List-of Num]
;; Given an _n_ argument function, and an argument list, calculates its _n_ partial derivates.
(define (partial-derivs F params)
(build-list
(length params) ;; For every parameter to F
(λ (n)
(local (;; Add epsilon to the nth parameter, and leave the others unchanged.
[define params+epsilon
(map/index
(λ (i p) (if (= i n) (+ EPSILON p) p))
params)])
;; We receive a list of parameters for F.
(/ (- (apply F params+epsilon) (apply F params)) EPSILON)))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define-struct gradient (grad error) #:transparent)
;; gradient-of-loss : (Num ... -> Num) [List-of Num] [List-of Num] -> (make-gradient [List-of Num] Num]
;; Given a function of _n_ parameters, a list of _params_, and an _expected-result_, calculates the
;; gradient and the squared error.
(define (derivs-of-loss F/args params expected-result)
(local ([define (F-loss . params)
(sqr (- expected-result (apply F/args params)))])
(make-gradient (partial-derivs F-loss params)
(sqr (- expected-result (apply F/args params))))))
;; update-params : Num [List-of Num] [List-of Num] -> [List-of Num]
;; Adds the gradients (multiplied by the learning rate) to the parameters.
(define (update-params lr params gradients)
(map (λ (p d) (- p (* lr d))) params gradients))
(define-struct solution (params error) #:transparent)
;; optimize : Num (Num ... -> Num) [List-of Num] [List-of [List-of Num]] [List-of Num]
;; -> (make-solution [List-of Num] Num)
;; Calculates new parameter values by adding the given parameters to the derivate of the loss
;; (at the given data points), scaled by the learning rate.
(define (optimize lr F params args-list expected-result-list)
(foldr
(λ (args expected sol)
(local ([define F/args (apply F args)]
[define one-grad (derivs-of-loss F/args (solution-params sol) expected)])
(make-solution
(update-params lr (solution-params sol) (gradient-grad one-grad))
(+ (gradient-error one-grad) (solution-error sol)))))
(make-solution params 0)
args-list
expected-result-list))
(define (opt-until max-rounds lr F initial-params data)
(local ([define args-from-data (map (λ (p) (list (first p))) data)]
[define results-from-data (map (λ (p) (second p)) data)]
[define (helper round sol)
#;(when (zero? (modulo round 100))
(printf "~a~n" (plot (list (points data) (function (λ args (apply (apply F args) (solution-params sol))))))))
(if (zero? round)
sol
(helper (sub1 round) (optimize lr F (solution-params sol) args-from-data results-from-data)))])
(helper max-rounds (make-solution initial-params 0))))
;; Try 5,000. Wait for the loss to stop decreasing
(define (optimize-ex-data-1 rounds)
(opt-until rounds 0.0001 linear-at
'(0 0) ex-data-1))
#|
(plot
(list (points ex-data-1)
(function (λ (x) (+ (* m x) b)))))
|#