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

Email
GitHub
LinkedIn

CS2500 Fundamentals of Computer Science


Lecture 1 - Introduction

What is Computer Science?

Computer science is to computers as microscopes are to biology.

This course is about how to solve problems, NOT how to use the tools to solve problems. Learning universal computer science and not the tools.

The Course

The course website is on canvas

Piazza:

Homework:

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?

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:

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

But what about ‘real’ animations?

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

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)

Comments

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:

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

Designing Functions:

Designing Data:

Prompt: Create a function that takes in a numerical grade and returns a letter grade

Signature: num->grade : Number -> String Can be multiple lines to define data types

Purpose Statement: Given a numeric grade, produces a letter grade

Function Template: Used to copy and paste for similar functions (such as lettergrade->gpa, lettergrade->passing?)

; letter-grade-template : LetterGrade -> ?

#| (define (letter-grade-template lg)
	(cond
	[(string=? lg "A") ...]
	[(string=? lg "B") ...]
	[(string=? lg "C") ...]
	[(string=? lg "D") ...]
	[(string=? lg "F") ...]))
|# ;This is a block comment

Examples (check-expects): Examples of what inputs lead to what outputs

The Funtion Body: the function itself

; A NumericGrade is a real number in [0,100]
; Interpretation: A student's numeric grade in Fundies I.

; A LetterGrade is a one of
; - "A"
; - "B"
; - "C"
; - "D"
; - "F" ; An enumerated data definition
; Interpretation: A student's letter grade is Fundies I.

; num->grade : NumericGrade -> LetterGrade
; Given a numeric grade, produces a letter grade
(check-expect (num->grade 93) "A")
(check-expect (num->grade 88) "B")
(check-expect (num->grade 72) "C")
; Unreasonable Examples
(check-expect (num->grade -10) "F")
(check-expect (num->grade 101) "A")

(define (num->grade n)
	(cond
		[(>= n 90) "A"]
		[(>= n 80) "B"]
		[(>= n 70) "C"]
		[(>= n 60) "D"]
		[(< n 40) "F"]))


; A LetterGrade is a one of
; - "A"
; - "B"
; - "C"
; - "D"
; - "F"
; Given a letter grade, determine if it is a passing grade.
; grade->passing? : LetterGrade -> Boolean
(define (grade->passing? lg)
	(cond
	[(string-equals? lg "A") #true]
	[(string-equals? lg "B") #true]
	[(string-equals? lg "C") #true]
	[(string-equals? lg "D") #false]
	[(string-equals? lg "F") #false]))


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

Functions:

next-light - Given a traffic light, return the next color

Animation

so instead we have to use…

Big-Bang

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

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

Data + Examples

Information vs. Data: Information is the interpretation of data

BAD WAY of representing this data:

"Jane Doe 3.9 #false"

This is bad because it’s all in a single string. Someone with a first name with a space in it can break it. For example:

"Jin Ho Kim 3.9 #false"

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

Structures

define-struct

student? (replace with structure name) is a predicate that returns if a value is of type student (or whatever other structure)

Structure Function Template

; 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

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

; two-balls-template : Two-Balls -> ?
(define (two-balls-template tb)
	(... (ball-template (two-balls-ball1 tb)) ...
	     (ball-template (two-balls-ball2 tb)) ...))

You don’t have to understand everything at any given time

draw-two-balls

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

Piazza has clarification on homework

Homework

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.

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

Pies

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

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

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.

For HW examples you need at least 3 examples. Make sure you have no Halloween colors!

Structured data and unions are more powerful than we have demonstrated so far.

Example with Employees:

(define-struct fulltime [name salary])
;; A FullTime is a (make-fulltime String Number)
;; Interpretation: A (make-fulltime n s) represents
;; a full time employee named n with annual salary s.

When you write a template, you tell yourself that functions that use the structure should use at least one piece of information from the structure.

;; fulltime-temp : FullTime -> ?
(define (fulltime-template ft)
  ; Translation: Do something with (fulltime-name ft) and/or
  ; (fulltime-salary ft)
  (... (fulltime-name ft) ... (fulltime-salary ft) ...))

Formal Definitions:

Informal Definitions:

Both fulltime and interns are employees.

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

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!

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?

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

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

Doll Example

Nesting dolls

(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

Lists

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

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

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!

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

Wants feedback for the class

Homework due date pushed back until Saturday

Mid-semester surveys

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

What is the Scene?

What Goes into the World State?

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

;; A Segments is a NEListofPosn
;;
;; Interpretation: The grid coordinates where the snake lies, the
;; position of the head is the first element of the NEList.
(define ex-segs-1 (cons (make-posn 4 4) (cons (make-posn 4 5) '())))
(define ex-segs-2 (cons (make-posn 4 3) ex-segs-1))
(define ex-segs-3 (cons (make-posn 3 3) ex-segs-2))

(define (segs-template ss)
  (cond
    [(empty? ss) ...]
    [(cons? ss) (... (first ss) ...
                     (segs-template (rest ss)) ...)]))

NEListofPosn = “non-empty list of Posns”

While doing a project, you should switch perspectives (high level vs. low level) frequently

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

Part II of the Class: Abstractions

Beginner Student Language → Intermediate Student Language

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

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

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

How can we have only 1 difference?

Create helper function that does the operation on a single number

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!

Lecture 18 - Expanded Abstraction

Recap on Abstraction

Apply-to-all

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

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

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


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

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

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

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

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

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.

Example

Creating filter (my-filter) using foldr.

<SLC - my-filter/v2>

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)

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

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)

Example:

(filter (lambda (s) (string=? s "hi")) (list "hi" "bye" "hi"))
; Returns: (list "hi" "hi")

“shit” - Arjun

make-adder using lambda:

;; make-adder : Number -> (Number -> Number)
(define (make-adder m)
	(lambda (n) (+ m n)))

Full Lecture Code

    ;; my-map : {X Y} (X -> Y) [List-of X] -> [List-of Y]
    (define (my-map f l)
      (cond
        [(empty? l) '()]
        [(cons? l) (cons (f (first l)) (my-map f (rest l)))]))

    ;; add-all-by : Number [List-of Number] -> [List-of Number]
    (define (add-all-by n l)
      (local (; helper : Number -> Number
              [define (helper m)
                (+ n m)])
        (map helper l)))

    ;; silly : Any -> (Number -> Number)
    #;(define (silly n)
      add-ten)

    ;; example-number : Number
    (define example-number 3487657845)

    #;(define f (silly "dfkjgidsfug"))
    ;; why : VOID ->  Function
    ;; why : (Number -> Number)
    ;; why : Number -> Number
    ;(define why add-ten)

    ;; make-adder : Number -> (Number -> Number)
    (define (make-adder m)
      (local (;; add : Number -> Number
              [define (add n)
                (+ m n)])
        add    ))

    ;; add-hundred : Number -> Number
    ;; add-hundred is add with (= m 100)
    (define add-hundred (make-adder 100))

    ;; add-five is add with (= m 5)
    (define add-five (make-adder 5))

    ; guessing-game : Number -> (Number -> String)
    (define (guessing-game n)
      (local (; guess : Number -> String
              [define (guess m)
                (cond
                  [(= m n) "Correct!"]
                  [(< m n) "Go higher!"]
                  [(> m n) "Go lower!"])])
        guess))

    ;; add-ten : Number -> Number
    (define (add-ten n)
      (+ n 10))

    (define add-ten/v2 (lambda (n) (+ n 10)))

    ; (filter (lambda (s) (string=? s "hi")) (list "hi" "bye" "hi"))

    ;; make-adder : Number -> (Number -> Number)
    (define (make-adder m)
      (lambda (n) (+ m n)))

    ;; add-hundred : Number -> Number
    ;; add-hundred is add with (= m 100)
    (define add-hundred (make-adder 100))

    ; (make-adder 100)
    ; ====>
    ; (lambda (n) (+ 100 n))

    ; (define add-hundred (lambda (n) (+ 100 n)))
    (define (add-hundred n) (+ 100 n))

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:

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:

Lambda

Short-hand for lambda is just λ.

Recall:

(map (λ (x) (+ x 10)) (list 1 2 3 4))
; Produces (list 11 12 13 14)

(map (λ (name) (string-append "Hi " name)) (list "Arjun" "Amal"))
; Produces (list "Hi Arjun" "Hi Amal")
; NOTE: Because it's a trival example, we can replace _name_ with just _x_.

Example:

;; Problem: design a function that consumes a list of strings and produces
;; those strings of length two in the list

;; only-two-strings : [List-of String] -> [List-of String]
(define (only-two-strings los)
  (filter (λ (s) (= (string-length s) 2)) los))

Example:

;; Problem: Design a funciton that consumes a list of strings and determines if
;; they are all strings of length two.

;; all-two-strings? : [List-of String] -> Boolean
(define (all-two-strings? los)
  (andmap (λ (s) (= (string-length s) 2)) los))

Example:

;; Design a function that consumes a list of numbers and only produces those
;; numbers that are within a given range.

; nums-in-range : Number Number [List-of Number] -> [List-of Number]
; Purpose: _(nums-in-range lo hi lon)_ produces those numbers in _lon_ that are
; greater than or equal to _lo_ and less than or equal to _hi_.
; [lo, hi].
(define (nums-in-range lo hi lon)
  (filter (λ (n) (and (<= lo n) (<= n hi))) lon))

NOTE: You cannot define a helper (non-local) function for this. The lambda calls lo and hi which wouldn’t be available outside the nums-in-range function.

You can also make the ‘helper’ local instead of lambda (exactly the same as if it were lambda).

Full Lecture Code

    ;; For later
    ;; mystery : [NE-List Number] -> Number
    (define (mystery lon)
      (/ (foldr + 0 lon) (foldr (lambda (x n) (+ 1 n)) 0 lon)))

    ;; A [List-of X] is one of:
    ;; - '()
    ;; - (cons X [List-of X])

    ;; An [NE-List X] is one of:
    ;; - (cons X '())
    ;; - (cons X [NE-List X])
    ;; Interpretation: A non-empty list of X.

    ;; ex-ne-list-1 : [NE-List Number]
    (define ex-ne-list-1 (list 900))
    ;; ex-ne-list-2 : [NE-List Number]
    (define ex-ne-list-2 (list 10 5 11 8))
    ;; ex-ne-list-3 : [NE-List String]
    (define ex-ne-list-3 (list "Fundies" "2500"))

    ;; TODO(arjun): The template below is not complete.
    (define (ne-list-template nel)
      (cond
        [(empty? (rest nel)) (... (first nel) ...)]
        [(not (empty? (rest nel))) (... (first nel) ...
                                        (ne-list-template (rest nel)) ...)]))

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

    ;; largest : [NE-List Number] -> Number
    (define (largest nel)
      (cond
        [(empty? (rest nel)) (first nel)]
        [(not (empty? (rest nel)))
         (if (> (first nel) (largest (rest nel)))
             (first nel)
             (largest (rest nel)))]))

    ;; Challenge: rewrite the function above using foldr and max

    (check-expect (largest (list 5 0 0 0 0 4)) 5)
    (check-expect (largest (list 4 0 0 0 0 5)) 5)
    (check-expect (largest (list 4 3 0 5 0 2)) 5)

    (define (largest/v2 nel)
      (cond
        [(empty? (rest nel)) (first nel)]
        [(not (empty? (rest nel)))
         (local ([define largest-in-rest (largest/v2 (rest nel))])
         (if (> (first nel) largest-in-rest)
             (first nel)
             largest-in-rest))]))

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

    ;; Problem: design a function that consumes a list of strings and produces
    ;; those strings of length two in the list.

    ;; only-two-strings : [List-of String] -> [List-of String]
    (define (only-two-strings los)
      (filter (λ (s) (= (string-length s) 2)) los))

    (only-two-strings (list "ab" "abc" "d" "de" "def" ""))

    ;; Problem: Design a function that consumes a list of strings and determines if
    ;; they are all strings of length two.

    ;; all-two-strings? : [List-of String] -> Boolean
    (define (all-two-strings? los)
      (andmap (λ (s) (= (string-length s) 2)) los))

    (check-expect (all-two-strings? (list "ab" "cd")) #true)
    (check-expect (all-two-strings? (list "ab" "" "cd")) #false)

    ;; Design a function that consumes a list of numbers and only produces those
    ;; numbers that are within a given range.

    ;; nums-in-range : Number Number [List-of Number] -> [List-of Number]
    ;; Purpose: _(nums-in-range lo hi lon)_ produces those numbers in _lon_ that are
    ;; greater than or equal to _lo_ and less than or equal to _hi_.
    ;; [lo, hi].
    (define (nums-in-range lo hi lon)
      (filter (λ (n) (and (<= lo n) (<= n hi))) lon))

    (check-expect (nums-in-range 4 6 (list 4 3 5 10 4 5 6 1))
                  (list 4 5 4 5 6))

    ;(define lo 0)
    ;(define hi 10)

    (define (num-in-range lo hi n)
      (and (<= lo n) (<= n hi)))

    (define (nums-in-range/v2 lo hi lon)
      (filter (num-in-range lo hi) lon))


    ;(nums-in-range/v2 0 10 (list -10 0 5 10 20))

    (define (nums-in-range/v3 lo hi lon)
      (local ([define (helper n)
                (and (<= lo n) (<= n hi))])
        (filter helper lon)))

    (define (num-in-range/v4 lo hi)
      (lambda (n)
        (and (<= lo n) (<= n hi))))

    (define (nums-in-range/v4 lo hi lon)
      (filter (num-in-range/v4 lo hi) lon))

    (nums-in-range/v4 0 10 (list -10 0 5 10 20))

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?

How Functions Work:

(lambda (x) (/ x 0))
; Does not throw an error (you need to call it to get the error)

“Lambdas fuck with your mental model of how things work” - Arjun

(define (func-a x y)
	(+ x (* 10 y)))

(func-a 2 300)
; ===>
(+ 2 (* 10 300))
; ===>
(+ 2 3000)
; ===>
3002

“I would hit the step button but everytime I do that, I feel this rage inside me” - Arjun

(define (my-map f l)
  (cond
    [(empty? l) '()]
    [(cons? l) (cons (f (first l)) (my-map f (rest l)))]))

(define (add10 n) (+ n 10))
;(my-map add10 (list 1 2 3))
; ===>
;(cons (add10 (first (list 1 2 3))) (my-map add10 (rest (list 1 2 3))))
; ===>
;(cons (add10 1) (my-map add10 (list 2 3)))
; === ..... ===>
;(cons (add10 1) (cons (add10 2) (cons (add10 3) (my-map add10 '()))))
;; 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?

(define ex-set-1 (list 1 3 5))
(define ex-set-2 (list 5 3 1))
; Invalid example: (define ex-set-3 (list 1 1 3 3 5 5))

These are all the same set, but they are different lists

(define ex-set-4 (list "Arjun" "Amal" "Ben"))
;; A [Set X] is a [List-of X]
;; order is irrelevant; no duplicates allowed
;; union : {X} [Set X] [Set X] -> [Set X]
(define (union set1 set2)
  (foldr add set2 set1))

(check-expect (union ex-set-1 ex-set-3) (list 1 3 5 2 4 6))

;(check-expect (union
;; intersect : {X} [Set X] [Set X] -> [Set X]

;; add : {X} X [Set X] -> [Set X]
(define (add elem set)
  (if (contains? elem set)
      set
      (cons elem set)))

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

;; contains? : {X} X [Set X] -> Boolean
(define (contains? elem set)
  (ormap (lambda (elem-in-set) (equal? elem-in-set elem)) set))

(check-expect (contains? 5 ex-set-1) #true)
(check-expect (contains? 5 ex-set-2) #true)
(check-expect (contains? 50 ex-set-1) #false)

Using equals? is bad practice

Intersect not completed in this lecture.

Full Lecture Code

    #|
    (check-expect (countdown 5) "5 4 3 2 1 Blastoff!")

    ;; countdown : Number -> String
    (define (countdown n)
      (foldr
       string-append
       "Blastoff!"
       (build-list n (lambda (i) (string-append (number->string (- n i)) " ")))))
    |#
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

    #|
    (define (my-function x)
      (/ 1 0))
    |#

    ;(lambda (x) (/ x 0))

    ;((lambda (y) (/ 1 0)) 100)

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

    (define (func-a x y)
      (+ x (* 10 y)))

    ;(func-a 2 300)
    ; ===>
    ;'(+ 2 (* 10 300))
    ; ===>
    ;(+ 2 3000)
    ; ===>
    ;3002

    (define (my-map f l)
      (cond
        [(empty? l) '()]
        [(cons? l) (cons (f (first l)) (my-map f (rest l)))]))

    (define (add10 n) (+ n 10))
    ;(my-map add10 (list 1 2 3))
    ; ===>
    ;(cons (add10 (first (list 1 2 3))) (my-map add10 (rest (list 1 2 3))))
    ; ===>
    ;(cons (add10 1) (my-map add10 (list 2 3)))
    ; === ..... ===>
    ;(cons (add10 1) (cons (add10 2) (cons (add10 3) (my-map add10 '()))))

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

    ;(my-map add10 l)
    ; ====>
    #;(cond
        [(empty? l) '()]
        [(cons? l) (cons (add10 (first l)) (my-map add10 (rest l)))])

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

    ;;;;;;;;

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

    (define add10-all/v2 (make-add-all 10))

    ; (define add10-all/v2 (make-add-all 10))
    ; ===>
    ; (define add10-all/v2 (lambda (l)
    ;                        (map (lambda (i) (+ i 10)) l)))
    ; ===>
    ; (define (add10-all/v2 l)
    ;  (map (lambda (i) (+ i 10)) l))

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

    ; { 2, 4, 6, 8, 10 }
    ; { 4, 2, 8, 10, 6 }
    ; { 4, 2, 2, 2, 2, 8, 10, 6 }

    ; { 1, 3, 5 } U { 2, 4, 6 } = { 1, 2, 3, 4, 5, 6}

    ; { 1, 3, 5 } INTERSECT { 3, 5, 7 } = { 3, 5 }

    ; {}

    (define ex-set-1 (list 1 3 5))
    (define ex-set-2 (list 5 3 1))
    (define ex-set-3 (list 2 4 6))
    ; Invalid example: (define ex-set-3 (list 1 1 3 3 3 5))
    (define ex-set-4 (list "Arjun" "Amal" "Ben"))

    ;; A [Set X] is a [List-of X]
    ;; order is irrelevant; no duplicates allowed

    ;; (list x y z)
    ;; (cons x (cons y (cons z '())))
    ;; (foldr f base (cons x (cons y (cons z '()))))
    ;; (f x (f y (f z base)))
    ;; (union (list x y z) set2)
    ;; (add x (add y (add z set2)))

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

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

    (check-expect (union ex-set-1 ex-set-3) (list 1 3 5 2 4 6))

    ;(check-expect (union
    ;; intersect : {X} [Set X] [Set X] -> [Set X]

    ;; add : {X} X [Set X] -> [Set X]
    (define (add elem set)
      (if (contains? elem set)
          set
          (cons elem set)))

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

    ;; contains? : {X} X [Set X] -> Boolean
    (define (contains? elem set)
      (ormap (lambda (elem-in-set) (equal? elem-in-set elem)) set))

    (check-expect (contains? 5 ex-set-1) #true)
    (check-expect (contains? 5 ex-set-2) #true)
    (check-expect (contains? 50 ex-set-1) #false)

    (list ex-set-1)

Lecture 24 - More Practice with Lambda and Locals

Sets

Recap on Lecture 23 - building sets with lists

Recall:

;; A [Set X] is a [List-of X]
;; order is irrelevant; no duplicates allowed
;; union : {X} [Set X] [Set X] -> [Set X]
(define (union set1 set2)
  (foldr add set2 set1))

(check-expect (union ex-set-1 ex-set-3) (list 1 3 5 2 4 6))

;(check-expect (union
;; intersect : {X} [Set X] [Set X] -> [Set X]

;; add : {X} X [Set X] -> [Set X]
(define (add elem set)
  (if (contains? elem set)
      set
      (cons elem set)))

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

;; contains? : {X} X [Set X] -> Boolean
(define (contains? elem set)
  (ormap (lambda (elem-in-set) (equal? elem-in-set elem)) set))

(check-expect (contains? 5 ex-set-1) #true)
(check-expect (contains? 5 ex-set-2) #true)
(check-expect (contains? 50 ex-set-1) #false)

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

Characteristic Function

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

;; Alternate definition:
;; A [Set-of X] = X -> Boolean
;; Interpretation: A set of elements X, represented by their characteristic
;; function.

Example:

(define (ex-fset-1 x)
	(or (= x 0)
		 (= x 10)
		 (= x 7)))
; This is the same as {0, 7, 10}
(define (ex-fset-2 x)
	(or (even? x)
		  (= x 5)))
; This is the set of all even numbers and 5

Union as a Set:

(define (ex-fset-3 x)
	(or (ex-fset-1 x)
		  (ex-fset-2 x)))
; The union of fset-1 and fset-2

Intersect as a Set:

(define (ex-fset-3 x)
	(and (ex-fset-1 x)
		  (ex-fset-2 x)))
; The union of fset-1 and fset-2

Contains and Add:

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

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

“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

    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    ;; Adapted from Lecture 23

    (define ex-set-1 (list 1 3 5))
    (define ex-set-2 (list 5 3 1))
    (define ex-set-3 (list 2 4 6))
    ; Invalid example: (define ex-set-3 (list 1 1 3 3 3 5))
    (define ex-set-4 (list "Arjun" "Amal" "Ben"))

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

    (check-expect (union ex-set-1 ex-set-3) (list 1 3 5 2 4 6))

    ;; Exercise: write intersect

    ;; add : {X} X [Set X] -> [Set X]
    (define (add elem set)
      (if (contains? elem set)
          set
          (cons elem set)))

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

    ;; contains? : {X} X [Set X] -> Boolean
    (define (contains? elem set)
      (ormap (lambda (elem-in-set) (equal? elem-in-set elem)) set))

    (check-expect (contains? 5 ex-set-1) #true)
    (check-expect (contains? 5 ex-set-2) #true)
    (check-expect (contains? 50 ex-set-1) #false)

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

    ; setA = { 1, 3, 5 }
    ; setB = { 20, 40, 60 }
    ; setA * setB = { (1, 20), (1, 40), (1, 60), (3, 20), (3, 40), (3, 60), (5, 20), (5, 40), (5, 60) }

    (define-struct pair [left right])

      #;(list
       (map (lambda (b) (make-pair (first set-a) b)) set-b)
       (map (lambda (b) (make-pair (second set-a) b)) set-b)
       (map (lambda (b) (make-pair (third set-a) b)) set-b))

    ;; prod :: [Set X] [Set X] -> [Set (make-pair X Y)]
    (define (prod set-a set-b)
      (foldr
       append
       '()
       (map
        (lambda (a) (map (lambda (b) (make-pair a b)) set-b))
        set-a)))

    (define ex-set-prod-1 (list 1 3 5 9 10 4))
    (define ex-set-prod-2 (list 20 40 60))
    (check-expect (length (prod ex-set-prod-1 ex-set-prod-2))
                  (* (length ex-set-prod-1) (length ex-set-prod-2)))

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

    ;; "Characteristic function"
    (define (ex-fset-1 x)
      (or (= x 0)
          (= x 10)
          (= x 7)))

    (define ex-fset-1/v2
      (lambda (x)
        (or (= x 0)
            (= x 10)
            (= x 7))))

    (define (ex-fset-2 x)
      (or (even? x)
          (= x 5)))

    (define (ex-fset-3 x)
      (or (ex-fset-1 x)
          (ex-fset-2 x)))

    (define (ex-fset-4 x)
      (and (ex-fset-1 x)
           (ex-fset-2 x)))

    ;; Alternate definition:
    ;; A [Set-of X] = X -> Boolean
    ;; Interpretation: A set of elements X, represented by their characteristic
    ;; function.

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

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

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

    ;((fadd 500 ex-fset-1) 1000)

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

    (define (fadd-nonsense elem1 set)
      (lambda (elem2)
        (or (equal? elem2 elem1)
            (fcontains? elem2 set)
            (equal? elem2 78645897243687592))))

    ;; union : {X} [Set X] [Set X] -> [Set X]
    (define (funion set1 set2)
      (lambda (query-elem)
        (or (fcontains? query-elem set1)
            (fcontains? query-elem set2))))

    (define fset-empty (lambda (query-elem) #false))

    (define fset-avoid-this (lambda (query-elem) #true))

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

    ;; [Set Integer]

    ;; N is an integer in the range [0, 10]
    ;; [Set N]

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

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

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

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.

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
    [(empty? alist) (error "key not found")]
    [(cons? alist)
     (if (= search-key (pair-key (first alist)))
         (pair-value (first alist))
         (alookup search-key (rest alist)))]))

(check-error (alookup 0 ex-alist-empty))
(check-expect (alookup 881 ex-alist-nuids) "Amal Ahmed")
(check-expect (alookup 748 ex-alist-nuids) "Arjun Guha

But what if the association list is very long?

Structure things as trees rather than a list.

All of the left nodes have a smaller value and the right nodes have a greater value (kind of sorted)

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

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?

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

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
        [(empty? alist) (error "key not found")]
        [(cons? alist)
         (if (= search-key (pair-key (first alist)))
             (pair-value (first alist))
             (alookup search-key (rest alist)))]))

    (check-error (alookup 0 ex-alist-empty))
    (check-expect (alookup 881 ex-alist-nuids) "Amal Ahmed")
    (check-expect (alookup 748 ex-alist-nuids) "Arjun Guha")

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

    (define-struct leaf [])
    (define-struct node [left key value right])
    ;; A [BST X] is one of:
    ;; - (make-leaf)
    ;; - (make-node [BST X] Number X [BST X])
    ;; Constraint: In _(make-node left key value right)_ all the keys in _left_ are
    ;; less than _key_ and all the keys in _right_ are greater than _key_.

    #;(define (bst-template abst)
        (cond
          [(leaf? abst) ...]
          [(node? abst) (...
                         (bst-template (node-left abst) ...)
                         (node-key abst) ...
                         (node-value abst) ...
                         (bst-template (node-right abst) ...))]))

    (define LEAF (make-leaf))
    (define ex-bst-0 (make-leaf))
    (define ex-bst-1 (make-node LEAF 4 "Daniel" LEAF))
    (define ex-bst-2 (make-node LEAF 3 "Amal" ex-bst-1))

    (define ex-bst-3
      (make-node (make-node
                  (make-leaf)
                  7 "Aislin"
                  (make-leaf))
                 10 "Ben"
                 (make-node
                  (make-node (make-leaf)
                             15 "Ferd"
                             (make-leaf))
                  17 "John"
                  (make-leaf))))
    (define ex-bst-4
      (make-node ex-bst-2
                 5 "Arjun"
                 ex-bst-3))

    ;; lookup : {X} Number [BST X] -> X
    (define (lookup query-key abst)
      (cond
        [(leaf? abst) (error "nobody")]
        [(node? abst)
         #;(if (= query-key (node-key abst))
             (node-value abst)
             (if (< query-key (node-key abst))
                 (lookup query-key (node-left abst))
                 (lookup query-key (node-right abst))))
         (cond
           [(= query-key (node-key abst)) (node-value abst)]
           [(< query-key (node-key abst)) (lookup query-key (node-left abst))]
           ;; ; (> query-key (node-key abst))
           ;; [else (lookup query-key (node-right abst))]
           [(> query-key (node-key abst)) (lookup query-key (node-right abst))])]))

    (check-expect (lookup 7 ex-bst-4) "Aislin")
    (check-error (lookup 8 ex-bst-4))

Lecture 27 - More on Binary Search Trees

Exam Monday after next.

Recall Binary Search Trees:

All keys on the right of the nodes have a value higher and all of the keys on the left have a lower value.

You may write signatures for all definitions (not just functions)

(define-struct leaf [])
(define-struct node [left key value right])
;; A [BST X] is one of:
;; - (make-leaf)
;; - (make-node [BST X] Number X [BST X])
;; Constraint: In _(make-node left key value right)_ all the keys in _left_ are
;; less than _key_ and all the keys in _right_ are greater than _key_.

(define (bst-template abst)
    (cond
      [(leaf? abst) ...]
      [(node? abst) (...
                     (bst-template (node-left abst) ...)
                     (node-key abst) ...
                     (node-value abst) ...
                     (bst-template (node-right abst) ...))]))

Lookup Function

;; lookup : {X} Number [BST X] -> X
(define (lookup query-key abst)
  (cond
    [(leaf? abst) (error "key not found")]
    [(node? abst)
     (cond
       [(= query-key (node-key abst)) (node-value abst)]
       [(< query-key (node-key abst)) (lookup query-key (node-left abst))]
       [else ; (> query-key (node-key abst))
          (lookup query-key (node-right abst))])]))

Lookup Unordered

;; lookup-unordered : {X} Number [BST X] -> X
;; Looks up the key, but does not require the ordering constraint to hold.
(define (lookup-unordered query-key abst)
  (cond
    [(leaf? abst) (error "key not found")]
    [(node? abst)
     (cond
       [(= query-key (node-key abst)) (node-value abst)]
       [else
        (if (bst-contains? query-key (node-left abst))
         (lookup-unordered query-key (node-left abst))
         (lookup-unordered query-key (node-right abst)))])]))

Note: This is the homework problem 11 in homework 9

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

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

Function - bst-add10 and bst-add100

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

Full Lecture Code

    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    ;; Adapted from Monday's lecture

    (define-struct leaf [])
    (define-struct node [left key value right])
    ;; A [BST X] is one of:
    ;; - (make-leaf)
    ;; - (make-node [BST X] Number X [BST X])
    ;; Constraint: In _(make-node left key value right)_ all the keys in _left_ are
    ;; less than _key_ and all the keys in _right_ are greater than _key_.

    #;(define (bst-template abst)
        (cond
          [(leaf? abst) ...]
          [(node? abst) (...
                         (bst-template (node-left abst) ...)
                         (node-key abst) ...
                         (node-value abst) ...
                         (bst-template (node-right abst) ...))]))

    ;; LEAF : {X} [BST X]
    (define LEAF (make-leaf))

    ;; ex-bst-1 : [BST String]
    (define ex-bst-1 (make-node LEAF 4 "Daniel" LEAF))
    ;; ex-bst-2 : [BST String]
    (define ex-bst-2 (make-node LEAF 3 "Amal" ex-bst-1))
    ;; ex-bst-3 : [BST String]
    (define ex-bst-3
      (make-node (make-node LEAF 7 "Aislin" LEAF)
                 10 "Ben"
                 (make-node
                    (make-node LEAF 15 "Ferd" LEAF)
                    17 "John"
                    LEAF)))
    ;; ex-bst-4 : [BST String]
    (define ex-bst-4 (make-node ex-bst-2 5 "Arjun" ex-bst-3))

    ;; ex-bst-5 : [BST Boolean]
    (define ex-bst-5 (make-node LEAF 0 #true (make-node LEAF 10 #true LEAF)))

    ;; lookup : {X} Number [BST X] -> X
    (define (lookup query-key abst)
      (cond
        [(leaf? abst) (error "key not found")]
        [(node? abst)
         (cond
           [(= query-key (node-key abst)) (node-value abst)]
           [(< query-key (node-key abst)) (lookup query-key (node-left abst))]
           [else ; (> query-key (node-key abst))
              (lookup query-key (node-right abst))])]))

    (check-expect (lookup 7 ex-bst-4) "Aislin")
    (check-error (lookup 8 ex-bst-4))

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

    ;; bst-contains? : {X} Number [BST X] -> Boolean
    (define (bst-contains? query-key abst)
        (cond
          [(leaf? abst) #false]
          [(node? abst) (or
                         (= query-key (node-key abst))
                         (bst-contains? query-key (node-left abst))
                         (bst-contains? query-key (node-right abst)))]))

    ;; lookup-unordered : {X} Number [BST X] -> X
    ;; Looks up the key, but does not require the ordering constraint to hold.
    (define (lookup-unordered query-key abst)
      (cond
        [(leaf? abst) (error "key not found")]
        [(node? abst)
         (cond
           [(= query-key (node-key abst)) (node-value abst)]
           [else
            (if (bst-contains? query-key (node-left abst))
             (lookup-unordered query-key (node-left abst))
             (lookup-unordered query-key (node-right abst)))])]))

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

    ;; lookup : {X} Number [BST X] -> X

    ;; LEAF : {X} [BST X]
    ;; (define LEAF (make-leaf))

    ;; insert : {X} Number X [BST X] -> [BST X]
    (define (insert query-key new-value abst)
      (cond
        [(leaf? abst) (make-node LEAF query-key new-value LEAF)]
        [(node? abst)
         (cond
           [(= query-key (node-key abst)) (make-node (node-left abst)
                                                     query-key new-value
                                                     (node-right abst))]
           [(< query-key (node-key abst))
            (make-node (insert query-key new-value (node-left abst))
                       (node-key abst) (node-value abst)
                       (node-right abst))]
           [else ; (> query-key (node-key abst))
            (make-node (node-left abst)
                       (node-key abst) (node-value abst)
                       (insert query-key new-value (node-right abst)))])]))

    (check-expect (lookup -100 (insert -100 "Carter" ex-bst-4)) "Carter")

    (check-expect (lookup 17 (insert -100 "Carter" ex-bst-4)) "John")

    (define-struct pair (key val))

    ;; list->bst : {X} [List-of (make-pair Number X)] -> [BST X]
    (define (list->bst key-val-list)
      ; (foldr + 0 lon)
      (foldr
       (lambda (new-pair partial-bst)
         (insert (pair-key new-pair) (pair-val new-pair) partial-bst))
       LEAF
       key-val-list))

    (list->bst (list (make-pair 1 "Arjun") (make-pair 0 "Amal")))

    #;(define (bst-template abst)
        (cond
          [(leaf? abst) ...]
          [(node? abst) (...
                         (bst-template (node-left abst) ...)
                         (node-key abst) ...
                         (node-value abst) ...
                         (bst-template (node-right abst) ...))]))

    ;; bst-add10 : [BST Number] -> [BST Number]
    ;; Adds 10 to all numbers in the BST.

    ;; bst-add100 : [BST Number] -> [BST Number]
    ;; Adds 100 to all numbers in the BST.

    (define (bst-map f abst)
        (cond
          [(leaf? abst) (make-leaf)]
          [(node? abst) (make-node
                         (bst-map f  (node-left abst))
                         (node-key abst)
                         (f (node-value abst))
                         (bst-map f (node-right abst)))]))

Lecture 28 - Symbols and Symbolic Expressions

Exam on Monday

Exam

First Exam

Trees

Compiler/Interpretor

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

(symbol? 'foo) ; Returns #true
(symbol=? 'foo 'foo) ; Returns #true
'45 ; Returns the number 45
'"hello" ; Returns the string "hello"
'#true ; Returns the Boolean #true
'"Hello"5 ; Returns the String "Hello" and then the number 5
'(1 2 "hi" #true) ; Returns the list (list 1 2 "hi" #true).
; You can also nest lists by this (but don't nest the quote)
'(1 2 3 4 #true "hello" "again" x y z)
; Returns (list 1 2 3 4 #true "hello" "again" 'x 'y 'z)

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]

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)

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

3 Templates

Parallel Traveral

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

;; add-pairs : [List-of Number] [List-of Number] -> [List-of Number]
;; Constraints: the two lists have the same length.
(define (add-pairs alist blist)
  (cond
    [(and (empty? alist) (empty? blist)) '()]
    [(and (cons? alist) (cons? blist))
     (cons (+ (first alist) (first blist))
           (add-pairs (rest alist) (rest blist)))]))

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

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

    (check-expect (add-pairs (list 10 20 30) (list 1 2 3)) (list 11 22 33))
    (check-expect (add-pairs '() '()) '())
    ; (check-expect (add-pairs (list 10 20 30) (list 5 1000)) (list 15 1020 1030))
    ; (check-expect (add-pairs (list 10 20 30) (list 5)) (list 15))
    (check-error (add-pairs (list 10 20 30) (list 5)))

    #;(define (parallel-template alist blist)
        (cond
          [(and (empty? alist) (empty? blist)) ...]
          [(and (cons? alist) (cons? blist))
           (... (first alist) ... (first blist) ...
               (parallel-template (rest alist) (rest blist)))]))

    ;; list=? : {X} . [List-of X] [List-of X] -> Boolean

    (check-expect (list=? (list 10 20) (list 10 20)) #true)
    (check-expect (list=? (list 10 20) (list 10 20 30)) #false)
    (check-expect (list=? '() '()) #true)
    (check-expect (list=? (cons 10 '()) '()) #false)

    (define (list=? alist blist)
      (cond
        [(and (empty? alist) (empty? blist)) #true]
        [(and (cons? alist) (cons? blist))
         (and (= (first alist) (first blist))
              (list=? (rest alist) (rest blist)))]
        #;[(and (cons? alist) (cons? blist))
         (if (= (length alist) (length blist))
             (and (= (first alist) (first blist))
                  (list=? (rest alist) (rest blist)))
             #false)]
        [(and (cons? alist) (empty? blist)) #false]
        [(and (empty? alist) (cons? blist)) #false]))

Lecture 30 - Parallel and Black-Box Traversial

Recall the templates from Lecture 29.

my-append

(define (my-append alist blist)
  (cond
    [(empty? alist) blist]
    [(cons? alist) (cons (first alist) (my-append (rest alist) blist))]))

But if blist doesn’t change, how can we optimize this so it doesn’t take in blist?

;; my-append : {X} . [List-of X] [List-of X] -> [List-of X]
(define (my-append/v3 alist blist)
  (local (;; helper : [List-of X] -> [List-of X]
          [define (helper l)
            (cond
              [(empty? l) blist]
              [(cons? l) (cons (first l) (helper (rest l)))])])
    (helper alist)))

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

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

List-ref

list-ref - Returns the nth element of a list

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

my-list-ref

;; my-list-ref : [List-of X] Nat -> X
(define (my-list-ref/v1 alist index)
  (if (= index 0)
      (first alist)
      (my-list-ref/v1 (rest alist) (- index 1))))

What are different ways of writing this function? Can we write this with parallel traversial?

(define (my-list-ref/v2 alist index)
  (cond
    [(empty? alist) (error "invalid index")]
    [(and (cons? alist) (zero? index)) (first alist)]
    [(cons? alist) (my-list-ref/v2 (rest alist) (- index 1))]))

list=?

Making a more general definition of list=? (because the previous definition only compared numbers)

;; list=? : {X} . (X X -> Boolean) [List-of X] [List-of X] -> Boolean
(define (list=? compare alist blist)
  (cond
    [(and (empty? alist) (empty? blist)) #true]
    [(and (cons? alist) (cons? blist))
     (and (compare (first alist) (first blist))
          (list=? compare (rest alist) (rest blist)))]
    [else #false]))
(define-struct person [name father mother])
;; An FT (family tree) is one of:
;; - 'none
;; - (make-person String FT FT)
;;
;; Interpretation: A family tree is either:
;; - _'none, which indicates that this ancestor is unknown
;; - _(make-person name father mother)_ which represents _name_ on the family
;;   tree, with _mother_ as the family tree of _name_'s mother, and _father_
;;   as the family tree of their father.

(define ex-qe2-ancestors
  (make-person "QE2"
               (make-person "George VI" 'none 'none)
               (make-person "Elizabeth BL" 'none 'none)))
(define ex-royalty
  (make-person "William"
               (make-person "Charles"
                            (make-person "Philip" 'none 'none)
                            ex-qe2-ancestors)
               (make-person "Diana" 'none 'none)))

;; ft=? : FT FT -> Boolean

(define (ft=? ft1 ft2)
  (cond
    [(and (person? ft1) (person? ft2))
     (and (string=? (person-name ft1) (person-name ft2))
          (ft=? (person-father ft1) (person-father ft2))
          (ft=? (person-mother ft1) (person-mother ft2)))]
    [(and (symbol? ft1) (symbol=? ft1 'none)
          (symbol? ft2) (symbol=? ft2 'none)) #true]
    [else #false]))
    ;[(and (person? ft1) (symbol? ft2) (symbol=? ft2 'none)) #false]
    ;[(and (symbol? ft1) (symbol=? ft1 'none) (person? ft2)) #false]))

(check-expect (ft=? ex-royalty ex-royalty) #true)
(check-expect (ft=? ex-royalty ex-qe2-ancestors) #false)

;; An Ancestor is either
;; - "mother"
;; - "father"
;; An AP (Ancestor Path) is a [List-of Ancestor]

;; find-ancestor : FT AP -> String
(define (find-ancestor ft ap)
  (cond
    [(and (person? ft) (empty? ap)) (person-name ft)]
    [(and (person? ft) (cons? ap))
     (if (string=? (first ap) "father")
         (find-ancestor (person-father ft) (rest ap))
         (find-ancestor (person-mother ft) (rest ap)))]
    [else (error "dunno")]))
    ;[(and (symbol=? ft 'none) (empty? ap)) (error "dunno")]
    ;[(and (symbol=? ft 'none) (cons? ap)) (error "dunno")]))


(check-expect (find-ancestor ex-royalty (list "father" "mother"))
              "QE2")
(check-expect (find-ancestor ex-royalty
                             (list "father" "mother" "mother"))
              "Elizabeth BL")

(define-struct node (name following))

;; A Twitter graph is a:
;; [List-of (make-node String [List-of String])]
;; CONSTRAINT: Any follower is an actual node in the graph

(define ex-twitter-1
  (list (make-node "A" (list "D" "E"))
        (make-node "B" (list "D"))
        (make-node "C" (list "A"))
        (make-node "D" (list "B"))
        (make-node "E" empty)))

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

Grades will be back by (at least) Friday

One more assignment left

Monday’s Lecture

Accumulators

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

Make a helper function

;; sum-to : [List-of Number] -> [List-of Number]
(define (sum-to lon)
  (modified-sum-to 0 lon))

;; sum-so-far is the *accumulator*
(define (modified-sum-to sum-so-far lon)
  (cond
    [(empty? lon) '()]
    [(cons? lon)
     (local ([define new-sum-so-far (+ sum-so-far (first lon))])
       (cons new-sum-so-far
             (modified-sum-to new-sum-so-far (rest lon))))]))

sum-so-far is the accumulator

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

Graphs (or network)

Trees

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

Edges - Arrows between people

Nodes - The people themselves (or vertices)

Neighbors - Nodes that are immediately adjacent

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

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

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.

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

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

Concluding regular programming today

Then random stuff

< No code posted :( >

Generative Recursion

Recall new line function (see Lecture 34 for more)

Insertion Sort

<slc - sort< >

Quick Sort (or at least the essense of Quick 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?

Gradient Descent

“The linear formula is y=mx+b. I’m going to massage this a little bit” - Arjun

Gradient is just a fancy term for slope.

Guess the slope and then guess the y-intercept

(F 5) ⇒ 53

(F 3) ⇒ 33

What is the function?

We need to guess the slope first. If you get lucky and guess 10 and 3 for the slope and y-intercept respectively you get the following:

((linear 5) 10 3) ⇒ 53

((linear 3) 10 3) ⇒ 33

How can we do better than just blind guessing?

How much should you vary between guesses?

(deriv (lambda (slope) (- (F 5) ((linear 5) slope 3))) 7 0.0001) ⇒ ~5.0000

“I’m closing my door because my cat is dying” - Arjun

Recall code from yesterday

Intro to 3D graphing

By using a 3D graph, we can better represent changing both m and b in the function y=m*x+b (recall that we already know x)

(require plot)

(define ex-linear (λ (x) (+ (* 2 x) -2)))

;; linear-at : Num -> (Num Num -> Num)
;; Represents _y = mx + b_. But with two tricks:
;; - _x_, _m_ and _b_ are all parameters
;; - The function first receives _x_ and produces a function that receives _m_ and _b_
(define linear-at
  (lambda (x)
    (lambda (m b)
      (+ (* m x) b))))

;; A plot of the two-argument function:
;;
;; f(x,y) = 2xy + x^2 + 3y
;;
;; Evaluate (plot3d ex-3d-plot)
(define (show-3d-plot-1)
  (plot3d (surface3d (λ (x y) (+ (* 2 x y) (* x x) (+ 3 y))) -1 1 -1 1)))

NOTE: You can’t get the derivative of absolute value which is why we square to get the ‘error’

The particular algorithm is called Gradient Descent

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))))
    (define (show-quadratic)
      (plot (function ex-quadratic -3 3)))

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

    (define (show-quadratic-at-2)
      (plot3d
       (list
        (surface3d (quadratic-at 2) -3 3 -3 3)
        (points3d (list (list 2 -2 (ex-quadratic 2)))))
       #:x-label "a axis"
       #:y-label "b axis"
       #:z-label "y axis"
       #:title "Fixed x = 2"))

    (define ex-quadratic-error (λ (a b) (sqr (- (ex-quadratic 2) ((quadratic-at 2) a b)))))

    (define (show-quadratic-error)
      (plot3d
       (surface3d ex-quadratic-error -3 3 -3 3)
         #:x-label "a axis"
         #:y-label "b axis"
         #:z-label "y axis"
         #:title "Fixed x = 2"))

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

    ;; Sum of errors of multiple points
    (define (linear-error x-values y-values)
      (λ (m b)
        (foldr + 0 (map (λ (x y) (sqr (- y ((linear-at x) m b)))) x-values y-values))))

    (define (plot-linear-error x-values y-values)
      (plot3d
       (surface3d (linear-error x-values y-values) -5 5 -5 5)
       #:x-label "m axis"
       #:y-label "b axis"
       #:z-label "y axis"))

    (define ex-data-1 '((-0.3993 0.787) (0.425 4.924) (-0.0895 2.6) (0.153 3.545) (-0.4466 0.387) (0.369 4.929) (0.3955 5.35) (-0.338 0.33) (0.1048 3.33) (-0.1397 1.63) (-0.4474 1.002) (-0.2395 2.338) (0.3424 5.48) (-0.1258 2.485) (0.4866 6.24) (-0.1342 2.593) (0.449 4.994) (0.088 2.462) (0.4666 5.70) (0.04956 3.06) (0.4816 5.19) (0.1378 3.393) (-0.2014 2.224) (-0.4887 0.3273) (-0.2225 1.88) (-0.1998 2.72) (-0.0908 1.796) (-0.3513 1.535) (-0.496 0.722) (-0.02463 1.415)))

    (define (plot-ex-data-error)
      (plot-linear-error (map first ex-data-1) (map second ex-data-1)))

    ;(plot-linear-error '(1 2 3) '(2 4 6))

    ; Cannot get to zero error on this example:
    ; (plot-linear-error '(1 2 3) '(-2 5 -10))

    ;; High-level idea:
    ;;
    ;; 1. Assume we have x-values and y-values (the *training data*)
    ;; 2. Guess values for m and b (the *parameters* of the model)
    ;; 3. Calculate the error (the *loss*)
    ;; 4. Is the loss acceptable? Return the current parameters
    ;; 5. Pick new values the parameters. Goal is to go "down the slope", i.e., negative of the derivate
    ;; 6.

    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    ;; Partial Derivatives

    ;; How precise do we want our numeric derivates to me?
    (define EPSILON 0.00001)

    ;; map-index: {X Y} (Nat X -> Y) [List-of X] -> [List-of Y]
    ;; Similar to map, but also gives the position of the element to _f_.
    (define (map/index f alist)
      (local (;; map-index/helper : Nat [List-of X] -> [List-of Y]
              [define (map/index-helper index alist)
                (cond
                  [(empty? alist) '()]
                  [else (cons (f index (first alist)) (map/index-helper (+ 1 index) (rest alist)))])])
        (map/index-helper 0 alist)))

    ;; partial-deriv : (Num ... -> Num) [List-of Num] -> [List-of Num]
    ;; Given an _n_ argument function, and an argument list, calculates its _n_ partial derivates.
    (define (partial-derivs F params)
      (build-list
       (length params) ;; For every parameter to F
       (λ (n)
         (local (;; Add epsilon to the nth parameter, and leave the others unchanged.
                 [define params+epsilon
                   (map/index
                    (λ (i p) (if (= i n) (+ EPSILON p) p))
                    params)])
           ;; We receive a list of parameters for F.
           (/ (- (apply F params+epsilon) (apply F params)) EPSILON)))))

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

    (define-struct gradient (grad error) #:transparent)
    ;; gradient-of-loss : (Num ... -> Num) [List-of Num] [List-of Num] -> (make-gradient [List-of Num] Num]
    ;; Given a function of _n_ parameters, a list of _params_, and an _expected-result_, calculates the
    ;; gradient and the squared error.
    (define (derivs-of-loss F/args params expected-result)
      (local ([define (F-loss . params)
                (sqr (- expected-result (apply F/args params)))])
        (make-gradient (partial-derivs F-loss params)
                       (sqr (- expected-result (apply F/args params))))))

    ;; update-params : Num [List-of Num] [List-of Num] -> [List-of Num]
    ;; Adds the gradients (multiplied by the learning rate) to the parameters.
    (define (update-params lr params gradients)
      (map (λ (p d) (- p (* lr d))) params gradients))

    (define-struct solution (params error) #:transparent)

    ;; optimize : Num (Num ... -> Num) [List-of Num] [List-of [List-of Num]] [List-of Num]
    ;;         -> (make-solution [List-of Num] Num)
    ;; Calculates new parameter values by adding the given parameters to the derivate of the loss
    ;; (at the given data points), scaled by the learning rate.
    (define (optimize lr F params args-list expected-result-list)
      (foldr
       (λ (args expected sol)
         (local ([define F/args (apply F args)]
                 [define one-grad (derivs-of-loss F/args (solution-params sol) expected)])
           (make-solution
            (update-params lr (solution-params sol) (gradient-grad one-grad))
            (+ (gradient-error one-grad) (solution-error sol)))))
       (make-solution params 0)
       args-list
       expected-result-list))

    (define (opt-until max-rounds lr F initial-params data)
      (local ([define args-from-data (map (λ (p) (list (first p))) data)]
              [define results-from-data (map (λ (p) (second p)) data)]
              [define (helper round sol)
                #;(when (zero? (modulo round 100))
                  (printf "~a~n" (plot (list (points data) (function (λ args (apply (apply F args) (solution-params sol))))))))
                (if (zero? round)
                    sol
                    (helper (sub1 round) (optimize lr F (solution-params sol) args-from-data results-from-data)))])
        (helper max-rounds (make-solution initial-params 0))))

    ;; Try 5,000. Wait for the loss to stop decreasing
    (define (optimize-ex-data-1 rounds)
      (opt-until rounds 0.0001 linear-at
                 '(0 0) ex-data-1))
    #|
    (plot
       (list (points ex-data-1)
             (function (λ (x) (+ (* m x) b)))))
    |#