Notes: end of class, 1/29

01-29-notes.rkt

#lang racket

;; CIS352 'S26 -- 1/29 through 2/3

;; □ -- More practice with lambdas
;; □ -- Mapping
;; □ -- Explaining recursion and why it matters
;; □ -- Our first non-list recursive type: trees
;; □ -- Pattern matching

;; Lambdas are often called "anonymous functions," because of the
;; fact that lambdas can be lifted out into top-level functions.
;;
;; For example, when we write
((lambda (x) (+ x 1)) 5)

;; We could have written
(define (anonymous-function1 x) (+ x 1))
(anonymous-function1 5)

;; QuickAnswer

;; Translate the following to "lift" both lambdas to top-level functions
;; Your answer should be two `define`s and a single transformed
;; expression that avoids using lambda at all.
;; ((λ (x) x) (λ (y) 5))
; (define (e0 x) x)
; (define (e1 y) 5)
(define e0 (λ (x) x))
;(e0 e1)

;(define (anonymousfunction (x) x) (anonymousfunction (y) 5))

;; This is what I call the "superficial" perspective on lambdas:
;; they are a syntactic nicety that allows us to write code that
;; immediately defines a function where it will be used. When
;; we write code using lambdas, it often allows us to be more direct,
;; write shorter code, etc.
;;
;; We will see later on that using λs unifies a lot of features
;; of functional programming, and we will take λ as one of the
;; foundational building blocks of programming. For now, we just
;; want to build some basic intuition with how to use it in our
;; code.
;;
;; Trivia: in Racket, λ and lambda are treated as the same
;; they are *not* equal? as symbols, i.e., (equal? 'λ 'lambda)
;; is false. But #lang racket defines λ and lambda to mean
;; the same thing. You can generally use them interchangably
;; when you write in Racket

;; Example: returning a lambda
(define (compose g f) (λ (x0) (g (f x0))))

;; Notice how the *result* is a function.
(define id-num (compose sub1 add1))

;; QuickAnswer

;; (double f) should return a function that applies (f (f x))
;; to its argument x. E.g., ((double add1) 2) => 4
(define (double f)
  (compose f f)) ;; either: use compose, or write directly

;; This has more than one expression in the body
;(lambda (x) e0 e1)

#;(define (double++ f)
  (lambda (x) (add1) x)
  (double++ f 2))

;; QuickAnswer

;; Repeat the function f n times.
;; (repeat 0 f) = (λ (x) x)
;; (repeat 1 f) = f
;; (repeat 2 f) = (λ (x) (f (f x)))
;; 
;; Think carefully about how to use the base case, you should
;; be calling (repeat (- n 1) f) and applying it in the recursive
;; case.
(define (repeat n f) ;; decreasing on n, f is the same for each call
  (if (equal? n 0)
      'base-case
      'recursive-case))

; ((repeat 5 add1) 5)

;; □ -- Mapping over lists

;; Mapping a function over a list applies each element to the function
(define (map f l)
  (if (empty? l)
      '()
      (cons (f (first l)) (map f (rest l)))))

;; (map add1 '(1 2 3)) => '(2 3 4)

;; QuickAnswer

;; Use map plus a lambda to square every element in the list l
;; remember, map takes two arguments:
;; - a lambda to apply to each element of the list
;; - the list to apply it to (in this case, l)
(define (square-list l)
  'todo)

#; (define (square-list+ l)
  (define (f x) x)
  (define (g y z) (+ y z)))

;; Maps are ubiquitous across languages, for example here is
;; an example in JavaScript:
;;     const array = [1, 4, 9, 16];
;;     const mapped = array.map((x) => x * 2);
;; And here
;; 

;; □ -- What *is* recursion?

;; Many students feel they do not understand recursion, it is a
;; vague topic, many explanations feel bad. Recursion is often
;; seen as the vainglorious counterpart to iteration.

;; This segment of lecture is intentionally more advanced. We
;; will talk about these ideas multiple times, but try to follow
;; along as much as you can.

;; First: recursion is tied hand in hand with the notion of
;; *algebraic data*. We are not fully prepared to make rigorous
;; the full details of algebraic data types. But simply put:
;; algebraic data is the type of data you get by linking structures
;; together. Lists are one of the simplest algebraic types we
;; will see.

;; To be slightly rigorous about it:
;;
;; - A list must be *either*
;;   -> The empty list '()
;;   -> A cons cell, consisting of a first element, followed by
;;   another list.
;; - You know it's *nothing* else.

;; In Lean (formal tool for math), we would write:
;; 
;; inductive List (α : Type u)
;; | nil  : List
;; | cons : α → List → List
;;
;; From this datatype definition, Lean derives the shape of
;; recursion automatically (and in a way which is mathematically
;; rigorous). We will be semi-formal about it for a few weeks.
;; 
;; 0% expectation this makes sense now--but it where we're headed.
;; Lean requires us to give elements of the list a *type*.
;; In Racket, we can skip that because types are dynamic.

;; Quickanswer

;; Define (list? l), which should have three cases:
;; - If l is equal? to '(), return #t
;; - If l is a cons cell (test using cons?), return (list? (rest l))
;; - Else, return #f
(define (my-list? l)
  (cond [(equal? l '()) #t]
        [(cons? l)
         ;; doesn't matter what first is but does matter (rest l) is list?
         (my-list? (rest l))]
        [else #f]))

#;(define (my-list? l)
  (if (equal? l '())
    #t
    (if (cons? l)
        (my-list? (rest l))
         #f)))

#;(define (my-list? l)
  (if (equal? l '())
      #t
      (if (cons? l)
          (list? (rest l))
          #f)))

#;(define (my-list? l)
  (if (empty? l) #t (if (cons? l) (my-list? (rest l)) #f)))



;; Quickanswer

;; Define (listof f), which returns a function that accepts
;; any argument `l` and returns #t iff:
;;   - l is a list
;;   - every element of l satisfies `f`
(define (listof f)
  'todo)

;; Now, we are better prepared to answer:
;;   Question: "What *is* recursion?"
;; 
;; Answer: "Recursion is a technique to define functions that
;; work over *all* lists. Because we know *every* list will be built
;; by *either* the empty list, *or* a cons cell (where we *know* the
;; rest *has to be another list*): then, assuming we define a function
;; `f` such that...
;; - `f` defines what to do with the value '()
;; - `f` defines what to do with (cons hd tl):
;;    -> *Assuming* we know the result `(f tl)`
;; 
;; - By doing just these two things, we have *proven* the function
;;   f works on *all* lists l!
;; 
;; So in short: recursion is a way to both (a) define functions over
;; lists, that (b) automatically tells us that function will work
;; on lists of *arbitrary* size. If we use recursion, we get these
;; guarantees *for free*.

;; In previous lectures I gave you a "template" to follow and I
;; asserted that it corresponds to recursion:
(define (foo l)
  (if (empty? l)
      'base-case
      (let ([partial-result (foo (rest l))])
        'combine-first-l-with-partial-result)))

;; But where does this template come from?
;; 
;; Answer: it turns out (although we will not do it now), the
;; "shape" of the recursion is directly in correspondence with
;; the definition of lists.
;;
;; Soon, we will look at algebraic data types beyond simply
;; *lists*. In that case, our recursion will have a different--but
;; related structure.
;;
;; (Advanced note:)
;; As we will see later on, recursion is the computation-theoretic
;; analogue to mathematical induction. In fact, every time you
;; appeal to the inductive hypothesis, you are *calling a recursive
;; function*. We will see more of this later, no need to get it
;; at all quite yet.

;; □ -- Trees

;; Next, we'll look at our first non-list algebraic type: trees.
;;
;; A binary tree is either:
;; - The symbol 'empty
;; - The list `(node ,v ,l0 ,l1) where:
;;   -> l's first element is 'node
;;   -> l's second element is any value v
;;   -> l's third element l0 is also a tree?
;;   -> l's fourth element l1 is also a tree? 

;; For example, the following are tree?s
'empty
'(node 5 empty empty)
'(node 5
       (node 0 empty empty)
       (node 10 (node 7 empty empty) (node 12 empty empty)))

;; Quickanswer

;; Complete the definition of (tree? t)
;; 
;; A binary tree is either:
;; - The symbol 'empty
;; - The list `(node ,v ,l0 ,l1) where:
;;   -> l's first element is 'node
;;   -> l's second element is any value v
;;   -> l's third element l0 is also a tree?
;;   -> l's fourth element l1 is also a tree? 
(define (tree? t)
  (cond [(equal? 'empty) #t]
        [(and (list? t)
              (equal? (length t) 4) ;; node's length is exactly 4
              'todo-more-here)
         #t]
        [else #f]))

;; □ -- Recursion on trees

;; Previously, I said that the way in which we lay out our
;; recursion can be directly calculated (is in correspondence with)
;; the datatype itself. Thus, we should ask: what do recursive
;; functions over trees look like? I.e., how do we define a function
;; that works over *all* trees t?
;;
;; For a list, we define a recursive function `(f l)` by defining:
;;  - (f '())
;;  - (f (cons hd tl)) -- Assuming we know the result of (f tl)
;;  - Since all lists are one of these two, we have now defined
;;    the funtion over *all* lists.
;; 
;; - Like a list, there are only two ways to build a tree
;;   -> The symbol 'empty
;;   -> The four-element list `(node ,v ,t0 ,t1), where t0/t1 trees
;;
;; - Thus, to define a function `(f t)` over trees we must:
;;   -> Define (f 'empty)
;;   -> Define (f `(node ,v ,t0 ,t1))
;;      -> *Assuming* we know (f t0) and (f t1)

(define (tree-size t)
  (if (equal? t 'empty) ;; what is (tree-size 'empty)?
      0
      ;; we know it's a node
      (let ([t0 (third t)]   ;; get left subtree as t0
            [t1 (fourth t)]) ;; get right subtree as t1
        ;; result is 1 + size of left + right subtree
        (+ 1 (tree-size t0) (tree-size t1)))))

;; Quickanswer

;; Assume trees are repsented as above, please complete the
;; definition of `(tree-sum t)`. I have stubbed out the
;; definition:
(define (tree-sum t)
  (if (equal? t 'empty)
      0 ;; sum of the empty tree is 0
      (let ([e  (second t)]  ;; bind node's value as e
            [t0 (third t)]   ;; bind left subtree as t0
            [t1 (fourth t)]) ;; bind right subtree as t1
        'todo)))

;; □ -- Pattern matching

;; (Hoping to get here by Tuesday, Feb 3)