Eric Chapdelaine
Student at Northeastern University Studying Computer Science.
Notes
Projects
Articles
Resume

Email
GitHub
Instagram

# Lecture 1 - Introduction

What is Computer Science?

• Telling a computer what to do
• The science behind how computers run
• Problem solving

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

The course website is on canvas

• You need a Khoury College account
• We will be using Piazza

Piazza:

• Announcements
• Wiki for the class

Homework:

• Due Friday evenings (but should be done Thursday)
• Check all homework on Canvas

## Rules of Evaluation

Like the order of operations but for computer science

### Syntax of Arithmetic

$12 + 6-$

This is an example of incorrect syntax

### Semantics / Meaning

Shows how to go from a valid arithmetic expression to an answer.

$5 \times 7 + \frac{21}{3}$

Why does this equal 42?

• Order of operations (Rules of Evaluation)

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$)

# Lecture 2 - Intro to Dr Racket and Image Manipulation

## Homework

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

## DrRacket

Use the ‘Beginning Student Language’

Recall:

• 1+24 →(+ 1 ( 2 4))
• This makes the order of operations obvious
• Strings have to wrapped in double quotations

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)

### String Manipulation

(replicate 10 "hi ")
; "hi hi hi hi hi hi hi hi hi hi "


### Image Manipulation

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)


## Functions

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

1. The name of the function
2. The argument(s)
3. The body of the function

### DrRacket

(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))


; Include draw-sun function from previous example
(require 2htdp/universe)
(animate draw-sun) ; Input a function that will be incremented every
; tick


# Lecture 3 - Conditions and Functions

### Functions

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


## Racket

### Numbers in Racket:

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: ;

### Check-Expect

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!'  ### Stepper Shows how BSL uses substitiution in its code. Acts as a debugger. $f(t) = 30 - \frac{1}{2} 9.8^{2}$ ### Booleans Any yes/no or true/false answer. In BSL, they are represented by #true and #false ### Predicates A function that returns a boolean. Usually ends with ? and it’s pronounced ‘huh’. Example string? is pronounced string-huh? ## Sunset Problem (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'  ## Conditionals 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  # Lecture 4 - How to Write Functions 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)  ### Programming Style: Examples: • Having really long lines (usually 80 characters; 102 for this course) (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)  ## How do get started writing functions: • Function Signatures • Purpose Statement: Higher level (short) description for what the function does. • The Function Definition • The check-expects Designing Functions: • Signature • Purpose Statement • Function Definition Designing Data: • Data Definition • Interpretation • Examples 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]))  # Lecture 5 - Extended How to Write Functions ### Recap on Lecture 4 - How to Write Functions : 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 ### Lecture 5 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]))  # Lecture 6 - Big Bang and Helper Functions HW 2 - Do with the same partners at HW1 ## Recall from Lecture 5 - Extended How to Write Functions Writing a function that handles TrafficLights Datatype TrafficLight is an enumerated data list with three different possible String possibilities • “Green” • “Yellow” • “Red” Functions: next-light - Given a traffic light, return the next color • Only three different possible examples. Below is the exhuastive set of examples (which means that it’s essentially your function definition) • Red →Green • Yellow →Red • Green →Yellow ### Animation • Can’t use animate because it returns an incremented number which isn’t compatable with the TrafficLight datatype so instead we have to use… ### Big-Bang • More powerful than animate 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) 1. on-draw on initial state 2. on-tick creates new scene with given state 3. There can be more event handlers (see documentation for more information) ### Traffic Light Example Return a full image of traffic light with all colors and have the active on solid (with the others outlined) ### Helper Functions • A function that simplifies the main function by doing repeatative tasks in a different function 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])  # Lecture 7 - Structures HW: Give at least 3 ‘interseting’ examples • Have no Halloween colors • Don’t mindlessly tweak numbers ### Data + Examples • Make sure to test with the number 0 Information vs. Data: Information is the interpretation of data • Atomic Data • Strings • Booleans • Numbers • Interals • Ranges of numbers • Enumerated Data • ex. TrafficLight • Only a certain amount of options (usually a String) • Structured Data • Mix of different data types • Example: A student at Northeastern • First name (String) • Last name (String) • GPA (Number in range [0.0, 4.0]) • on-coop (Boolean) 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"  ## Structures (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 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])  ### Templates 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) ...))  ## Functions with Structures 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))))  ## Example: Ball in motion in two dimensions ; 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))  # Lecture 8 - Extended Structures 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 • For example, typing 13, returns 13 ## Structures define-struct • Only defines constructor functions student? (replace with structure name) is a predicate that returns if a value is of type student (or whatever other structure) ### Structure Function Template • Take things ‘out of the box’ ; student-template : student -> ? (define (student-template student) (... (student-first student) ... (student-last student) ... (student-gpa student) ... (student-on-coop student) ...))  ## Ball Example 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 • ex. draw-ball doesn’t use the velocity ## Two Balls DO 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 ### Template for two-balls • You can have nested templates ; two-balls-template : Two-Balls -> ? (define (two-balls-template tb) (... (ball-template (two-balls-ball1 tb)) ... (ball-template (two-balls-ball2 tb)) ...))  • Templates let’s you break down what you have to work with You don’t have to understand everything at any given time ### draw-two-balls • Remember to use helper functions • We already have draw-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))))  # Lecture 9 - Expanding BigBang and Short Circuits Piazza has clarification on homework Homework • Auto-grader catches syntax and style and it’s free points…USE IT • Refer to the style guide on the course website ### Recall from [[Lecture 8 - Extended Structures]] (define-struct ball [x y vx vy])  Nested structured data: (define-struct two-balls [ball1 ball2])  ### Templates 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))))  ## Let’s Make a Game! 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]))  ### Signatures 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  ## Short Circuits 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")))  # Lecture 10 - Unions and Structures We are building up to recurrsion Remeber that office hours are almost all of the time. Recommended to go on Monday ## Unions - Unbounded Number of Things ### Pie Data Definition • Type and are they nut free? ### Pies • Pecan Pies • Cream Pies • Fruit Pies • For every fruit pie, we need to know its type and if it has nuts ;; 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. ## Template • Fruit pies are a different type than the rest therefore we need to handle each condition differently. • Remeber: templates unpack the box as much as possible (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)  ### Location Example 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) ...]))  # Lecture 11 - Working with Unions 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: • What we’ve been doing; written in pseudo code Informal Definitions: • The English interpretation of what you want to do; expressed in comments. • Don’t do this Both fulltime and interns are employees. ### Data Definition - Union 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. ### Template (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)]))  ### Making a Function that Works with Unions 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 ### Data Definition with No Examples ;; 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% ### Templates with Unions ; Define the types of data: ; - (make-[structure] ...) ; - (make-[other_structure] ...)  ## Species Example ;; 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"))  # Lecture 12 - Into to Self Referential Data Saturday 10th - Exam study session (4-6pm) The lab tomorrow (Oct. 6th) explains how to take an exam Exam • Similar to the homework problems ## Intro into Self Referential Data 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! • It’s not scalible ### How do we have an arbatrary amount of TAs? (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 ### Template How can we unpack the box here? • Check to see if it’s a lab • Check to see if it’s an add-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 ### Example Function 1 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)))]))  ### Example Function 2 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)))]))  ### Example Function 3 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) )]))  # Lecture 13 - Continued Refferential Data Definitions ### Bullseye Example • Self refferential union (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))  ### Template 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 ### Example Function 1 - Count Rings ;; 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)))]))  ### Example Function 2 - Produce Black and White Rings ;; 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: • What should I do with the base case? • How am I processing each recursive case? • How do I put things together? ### Doll Example Nesting dolls • 2 Types of recursive data • Make sure, if yo use 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.  ## Lists 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.  # Lecture 14 - Lists and Midterm Prep ## Midterm • Next Wednesday at 6-9pm • Everything but lists • No electronics besides one computer • Open-ended questions • Review session this Saturday • Open note/book • Practice exam on Hourglass • Similar to homework • Remeber the design recipe ## Lists • Empty: '() • Create List: (cons 10 '()) • Selectors • First (ex. (first ex-list-1)): returns the first element of the list • Rest (ex. (rest ex-list-1)): Returns the second element of the list (aka the rest of the list) ### Data Definition and Template ;; 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) ### Example Function 1: Sum of Numberes ;; 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)) )]))  ### Example Function 2: Product of Numbers ;; 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))))]))  ### String Example 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)) ...)]))  • Not good to repeat code (we will learn a single template for lists later) ### PosnList Example ;; 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! • It won’t be scalable Posn-Structure: (make-posn x y) ### Example Function with POSN-LIST ;; 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)  # Lecture 16 - Intro to Snake Game ### Exam Yesterday • Tech issues! Didn’t go well • Thinking abpout options for the 2nd midterm • maybe just take home exam Wants feedback for the class • Have any problems? Homework due date pushed back until Saturday Mid-semester surveys • They are important • Long queue for Office Hours • Tweaks being implemented ## Building the Snake Game “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 • on-tick = move the snake • on-key = change direction of snake • on-draw = draw • stop-when = game over ### What is the Scene? • Everything of interest • Position of snake’s segments • Direction of snake ### What Goes into the World State? • Things that change/are updated • Everything else should just be a constant 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  ### Segments of the Snake • Self-referential 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)) ...)]))  NEListofPosn = “non-empty list of Posns” • The first one is the head and the last one is the tail • Remeber: the difference between sugments have to be 1 in the x or 1 in the y needs to be continuous • Make sure your examples are correct While doing a project, you should switch perspectives (high level vs. low level) frequently ### Snake Data Definition ;; 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-snake Function ;; 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  # Lecture 17 - Into to Abstraction Midterm grades will be released at the end of the day today Partner Switch • Only switch of the semester happens this week ## Part II of the Class: Abstractions Beginner Student Language → Intermediate Student Language • Lists can now be represented as (list 1 2 3 4 5) • Function (list? returns whether or not something is a cons or '() • This is useful for nested lists ’() can also be written as (list) ## Abstraction 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 • Bad practice ### Example 1: Prefixes ;; 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"))  • Reduces the repetition by taking out the similarity ### Example 2: Addition and Multiplication ;; 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 • Operation and number How can we have only 1 difference? Create helper function that does the operation on a single number • The only difference is the helper funciton they call ### You can have funcitons as function parameters!!! ;; 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 ### Signature What is the signature of apply-to-all? ;; apply-to-all : (Number -> Number) LON -> LON ;; apply-to-all : (String -> String) LOS -> LOS  More on this later! • Lambda expression # Lecture 18 - Expanded Abstraction ### Recap on Abstraction • You can send functions as function inputs • Helper functions are used to create a similar general funciton Apply-to-all • Performs a funciton on every element in a list ### Signature for 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” ### General Signature ; 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. ### Example 1: many-circles Almost 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 ### Example 2: give-evens • Cannot write this function using apply-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 • It will never call two recursive functions in the same layer. • Two options for recursion ### Example 3: give-capitalized Similar 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))  ## Abstracting Functions • Play spot the difference with the two functions • Make only one difference (use helper functions) ## Map and Filter Map: always produce a list of the same length Filter: input [List-of X], always returns [List-of X] # Lecture 19 - Scope and Local ### Things they want to teach • Theorietical foundations of computing • Design recipe • Mechanics of programming • Time spend on a keyboard ### Abstraction 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)))]  ### Check Syntax • Gives a graphical representation of where variables and functions come from • USE IT! ### Local Definitions: 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 • Still need a signature • Don’t use this for every helper function, only the ones that require it • The variables (including function inputs) pass from the main function to the helper function (see this in 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 ## Examples of Abstraction ### many-circles example How 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 example Multiply 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)))  ## Abstraction with 2 Differences (Challenge problem) Create an abstraction for sum-all and mul-all (that can be used for things that aren’t just numbers) There are two differences • Base case • Function called ;; 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 ### Signature ;; 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  ### Example: 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 ....))  # Lecture 20 - Built-in Abstraction Functions “I apologize for swearing. No, not really” - Arjun ## Programming with List Abstractions ### Map ; _(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 ; filter : {X} (X -> Boolean) [List-of X] -> [List-of X]  See previous lectures for more information. ### Foldr ; 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)))  ## Foldr ; 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. • All functions that use the 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. • Don’t have to use all arguments while making a function. foldr gives you all items, so if you don’t need it, don’t use it. Example Creating filter (my-filter) using foldr. • There are two recursive calls. So how can we make it look like the template? <SLC - my-filter/v2> • Notice that we used local to define the similarity in the my-filter function While 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. ### Build-list ; 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 ;; 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)  • If a function doesn’t have to be local, it’s easier to read if it’s global 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)  # Lecture 21 - Introduction to Lambda “I’ve only fallen asleep while talking once” - Arjun Things you can do with functions 1. Calling the function directly 2. Using it as an argument for another function 3. Put functions inside other functions using local 4. Write functions that return functions • Introduced this lecture ### Function as argument ;; add-ten : Number -> Number (define (add-ten n) (+ n 10))  (map add-ten (list 10 20 30))  Passing add-ten as a parameter ### Local Function ;; 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)))  • Uses local function ## Functions that Produce other Functions ;; 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 ### Example 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  ### Example 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))  ## Lambda 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)  • For internal help functions, this is very useful Example: (filter (lambda (s) (string=? s "hi")) (list "hi" "bye" "hi")) ; Returns: (list "hi" "hi")  • No need for check-expects, purpose statement, and signature for the lambda function “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))  # Lecture 22 - Local and Lambda ## Non-Empty List It’s often helpful to require for lists to be non-empty Examples for when the empty list is meaningless: • Minimum or Maximum of a list ### Data Definition: ;; An [NE-List X] is one of: ;; - (cons X '()) ;; - (cons X [NE-List X]) ;; Interpretation: A non-empty list of X.  ### Template: (define (ne-list-template nel) (cond [(empty? (rest nel)) (first nel)] [(not (empty? (rest nel))) (... (first nel) ... (ne-list-template (rest nel))...)]))  ### Example: 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 Function 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. ### Usage of Local: • Make functions easier to read • Make programs run faster ## Lambda Short-hand for lambda is just λ. • This can be produced with CTRL+\ (CMD on macOS). 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))  # Lecture 23 - Continuation on Lambda No lab quiz tomorrow! ### Continuation on Lambda (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? • One line functions should be • 4-5 lines should be the limit of the lambda ### How Functions Work: (lambda (x) (/ x 0)) ; Does not throw an error (you need to call it to get the error)  • Does not run body until function is called • The body of the function suspends computation “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 '()))))  • When you use 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)))  ### Sets 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?

• We only know how to make lists
• However, in lists, order does matter
(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)

(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]
(if (contains? elem set)
set
(cons elem set)))

(check-expect (add 10 ex-set-1) (list 10 1 3 5))

;; 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

• If we union { {1, 3, 5}, {2, 4, 6} } and { {5, 3, 1} }, it repeats the element {1, 3, 5}
• This is because 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))))
; ===>
; === ..... ===>

;;;;;;;;;;;;;;;;;;

; ====>
#;(cond
[(empty? l) '()]

;; add10-all : [List-of Number] -> [List-of Number]
(cond
[(empty? l) '()]

;;;;;;;;

;; make-add-all : Number -> ([List-of Number] -> [List-of Number])
(lambda (l)
(map (lambda (i) (+ i n)) l)))

; ===>
;                        (map (lambda (i) (+ i 10)) 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)

;; (union '() set2)
;; set2

;; union : {X} [Set X] [Set X] -> [Set X]
(define (union set1 set2)

(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]
(if (contains? elem set)
set
(cons elem set)))

(check-expect (add 10 ex-set-1) (list 10 1 3 5))

;; 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)


# Lecture 24 - More Practice with Lambda and Locals

## Sets

Recap on Lecture 23 - building sets with lists

• Limitations
• Can’t represent all possible sets (example all even numbers)
• We can, however, represent all finite sets

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)

(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]
(if (contains? elem set)
set
(cons elem set)))

(check-expect (add 10 ex-set-1) (list 10 1 3 5))

;; 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)



### Cartesian Product

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)))

• Nested mapfunctions (for each in the first list, handle each in the second list)

### Characteristic Function

Let’s not use lists to represent sets. Instead, let’s use functions

• Can represent infinite sets this way
• Don’t actually use in practice
• It’s a pain
;; 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


;; fcontains : X [Set X] -> Boolean
(define (fcontains? elt set)
(set elt))

;; fadd : {X} X [Set X] -> [Set X]
(lambda (elem2)
(or (equal? elem2 elem1)
(fcontains? elem2 set))))

• The reason that we use 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

;; 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))


### Complement

(define (fcomplement set)
(lambda (query-elem)
(not (fcontains query-elem set))))


Full Lecture Code

    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(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)

(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]
(if (contains? elem set)
set
(cons elem set)))

(check-expect (add 10 ex-set-1) (list 10 1 3 5))

;; 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]
(lambda (elem2)
(or (equal? elem2 elem1)
(fcontains? elem2 set))))

#;(define (ex-fset-1 x)
(or (= x 0)
(= x 10)
(= x 7)))

(check-expect (fcontains? 500 ex-fset-5) #true)
(check-expect (fcontains? 0 ex-fset-5) #true)
(check-expect (fcontains? 5000 ex-fset-5) #false)

(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]


# Lecture 25 - New Kinds of Self Referential Data

Unions of structs that are self-referential are more powerful than we initially thought.

## River Example

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

### Data Defintion:

;; 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))))


### Template:

;; 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)) ...)]))

• Notice the two recursive calls

### Function - 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

### Function - 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)))]))

• only change the base case between count-streams and flow-to-ocean

“Let’s make this a lamer tree” - Arjun

### Function - 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)))]))


## Tree Example

### Data Defintion

;; 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))))

• Two base cases
• Note: the reason that leaf is a structure itself is for two reasons
• So everything is the same type
• Future proof — we can add to it later

### Template

;; 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)) ...)]))


# Lecture 26 - Binary Trees

Exam on Nov. 23rd.

• Harder than the first exam
• It should take 1.5 hours, given 3 hours
• Material: from Day 1 to Right now

Error:

• (error [STRING]) : Produces Error

### Association List

(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
[(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?

• It might take very long
• Abstract data type

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)

• This allows us to limit which children we look at to save time

“Oh, wow. There’s like a phone with a curly thing.” - Arjun

### Example - Leaf and Nodes

(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?

• The example was arbitrary
• For this class, don’t worry about it. Just make sure that it’s not left or right leaning.

### Template

(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) ...))]))

• Note: we will learn a better way to do templates later

### Function - 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
[(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))


# Lecture 27 - More on Binary Search Trees

Exam Monday after next.

Recall Binary Search Trees:

• Leafs
• Nodes

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 Function

;; lookup : {X} Number [BST X] -> X
(define (lookup query-key abst)
(cond
[(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

;; 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
[(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

• But this isn’t that good because it searches the tree n times (where n is the height of the tree)

### Function - 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)))])]))

• Insert and lookup are the two functions that are actually used by the user
• We are assuming that keys are unique
• If it has the same key, we are replacing the node

“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

### Function - 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))

• Non-uniform fold
• Note: when you need two values, you can package them into a struct and ‘unbox’ them later on

### Function - bst-add10 and bst-add100

• These look similar to map

### Function - bst-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)))]))

• You can do (almost) all of the list abstractions in trees

Full Lecture Code

    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(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
[(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
[(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)))]))


# Lecture 28 - Symbols and Symbolic Expressions

Exam on Monday

• Do quiz on Canvas to see what to do about Lecture that day

Exam

• Everything (including today’s lecture)
• Signature detection
• List abstraction
• Foldr
• Trees
• Mutual Recursion
• Most likely on Hourglass Server
• Know by Thursday if it’s on handin or Hourglass

First Exam

• Write a Data Definition → Design a function

## Trees

• Multiple self-references
• Binary Search Trees
• Multiple self-references by comparisons

### Compiler/Interpretor

• A program that runs another program
• Ex. DrRacket is an compiler/interpretor
• What would the data definition for DrRacket be?
• The programs that we feed into DrRacket (the code) is the data itself

## Atomic Data

; 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)))


### Symbols

• Essentially a string that can’t have spaces
• However, they have meaning to a computer
• Denoted by a single ' at the beginning
• Shorthand for (quote ...
(symbol? 'foo) ; Returns #true
(symbol=? 'foo 'foo) ; Returns #true

• Comparing two symbols is nearly instant (compared to strings were its dependent on its length)
• You can’t do normal string operations on symbols. You can only compare two symbols against each other
'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)


### Program Representation

'(+ 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))


### Data Definition

; 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]

• These three data definitions (including Atom) is a complete representation of programs
• NOTE: SExpr and LOS are mutually self referential
• SExpr are just trees

### Examples

(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)))


### Example Problems

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)) ...)]))


# Lecture 29 - More on Symbolic Expression and Templates

2 more homework assignments (after this one)

## Symbolic Expression (SExpr)

• Atomic Data
• String
• Number
• Boolean
• Symbol
;; 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)))


### Example - Replace Instances of S-Expr and replace it

(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)))

• Challenge Round:
• Create a calculator using S-Expr that compiles to ISL
• Assume only +, *, -, / and all of the atoms are numbers

## 3 Templates

Template:

### my-append

;; 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.
(cond
[(and (empty? alist) (empty? blist)) '()]
[(and (cons? alist) (cons? blist))
(cons (+ (first alist) (first blist))

(check-expect (add-pairs (list 10 20 30) (list 1 2 3)) (list 11 22 33))


### list=?

(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.
(cond
[(and (empty? alist) (empty? blist)) '()]
[(and (cons? alist) (cons? blist))
(cons (+ (first alist) (first blist))

(check-expect (add-pairs (list 10 20 30) (list 1 2 3)) (list 11 22 33))
; (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]))


# Lecture 30 - Parallel and Black-Box Traversial

Recall the templates from Lecture 29.

### my-append

• black-box traversial (don’t change blist. 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)))

• Recursion can happen in a helper function as well

Challenge: use a list abstraction for the definition of my-append

(define (my-append/v2 l1 l2)
(foldr cons l2 l1))


### List-ref

list-ref - Returns the nth element of a list

(list-ref (list 10 20 30) 0) ; Returns 10

• Natrual means positive integer that include 0

### 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)

• Combines both parallel traversial and black-box traversial
;; 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]))

• You can also write this function using list abstractions

# Lecture 31 - Optional Lecture on Trees

(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

(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)))


# Lecture 32 - Accumulators and Graphs

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

• Operating systems
• Machine learning

Grades will be back by (at least) Friday

One more assignment left

• Covers what are doing in class today

### Monday’s Lecture

• Parallel traversial
• Graphs

## Accumulators

Return the list of sums of numbers up to a certain point in a list

Make a helper function

• lets forget about list abstractions
;; 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

• Notice that adding a new argument would make things easier
• And then you just initialize the accumulator to 0 in the main function

Challenge: solve-to using list template and no helper function

• This solution is more complicated and is less efficent

## Graphs (or network)

### Trees

“If you can work with trees, your life is relatively easy” - Arjun

• Unlike trees, graphs can cycle back to any point
• Ex. roads, social media, etc.
• Directed Graphs
• Only one direction is viable
• ex. Twitter - “I can choose to follow you, you don’t have to follow me back”
• Undirected Graphs
• Needs to be able to go both ways
• ex. Facebook - “Needs to be friends with each other”

Edges - Arrows between people

Nodes - The people themselves (or vertices)

Neighbors - Nodes that are immediately adjacent

### Turning this idea into code:

(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))


# Lecture 33 - Accumulators

Exam will be returned tomorrow morning

NOTE: Graphs are prime Software Engineer interview questions

• Accumulators won’t run out of memory like recursion will because it sends the completed (up to said point) value through again. In recursion it opens all of the stacks and then runs the functions.

## Reverse

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 '())))

• Remeber, we can make these helper functions local (this is an acceptable use of local)

## Foldl

;; 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))))


# Lecture 34 - Accumulators Generative Recursion

Exam grades will be released this evening.

• Average score was about 70 points (which is about 5 points lower than usual) — this hasn’t been a normal semester

Get involved with research and stuff!

## Accumulators

### Tree Example

(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))

• But this is slow
• We can use an accumulator for this:
;; 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 '()))


## Generative Recursion

• we’ve usually been using structrual recursion

apply - Function that takes in a list and uses every element in a list as arguments to the function input

# Lecture 35 - Generative Recursion and Machine Learning

What we should read over break in preperation of Fundies 2

• Google northeastern Fundies 2 (go over the lecture notes)
• Head First Java (book) is pretty good
• Online course?
• UCST Coursera course

Concluding regular programming today

Then random stuff

< No code posted :( >

## Generative Recursion

Recall new line function (see Lecture 34 for more)

• Notice: it didn’t follow the design recipe

### Insertion Sort

<slc - sort< >

<slc - qsort>

## Intro To Machine Learning

“Bascially all machine learning is recursion problems” - Arjun

### Rate of Change

<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

### Linear Regression

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

• This shows how much you jump

# Lecture 36 - Continued Machine Learning

“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’

• Term for the ‘error’ is L2-norm

The particular algorithm is called Gradient Descent

• Socastic Gradient Descent is what’s used in practice (we are ignoring the extra features)

### How to solve it:

1. We need to detremine what our model is going to be
1. The example that we’ve used has just been linear models
2. Need data (called training data)
3. Calculate the error (called the loss)
1. Often times an error of 0 is not possible
4. If the loss is acceptable, return current parameters
5. If the loss is not acceptable, pick new values for the parameters. Goal is to go “down the slope”

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)

### Partial Derivative

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))))

;; quadratic-at : Num -> (Num Num -> Num)
;; Represents _y = ax^2 + bx_.
(lambda (x)
(lambda (a b)
(+ (* a x x) (* b x)))))

(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"))

(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)))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; 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)))])
(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.
(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
(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)))))
|#
`