As usual, this is not a comprehensive review sheet, nor is it "official."

Linked Lists

Accessing parts of a list with first and rest

Recall that given any list, we can use first and rest to access its head and remainder, respectively:

(define my-list (list 1 true "hello" 50))

(first my-list)  ; 1
(rest my-list)   ; (list true "hello" 50)

Lists as cons pairs

Until now, you've been using lists as one-dimensional data structures:

(list 1 2 3)

It turns out that this list constructor function is just a convenient wrapper over the real structure of a list.

We use cons to build lists out of pairs, attaching a new item to an existing list:

; (list 1 2 3) is equivalent to
(cons 1
      (cons 2
            (cons 3 empty)))

; a single-element list
(cons 3 empty)

So lists are actually nested pairs like this:

+-----+-------------------------+
|     |-----+-----------------+ |
|     |     |-----+---------+ | |
|  1  |  2  |  3  |  empty  | | |
|     |     |-----+---------+ | |
|     |-----+-----------------+ |
+-----+-------------------------+
 first          rest

Formally, a List-of-X is one of:

• empty
• (cons X List-of-X)

Note that this is a recursive definition. A recursive definition uses the term being defined (in this case, List-of-X) within its definition (in this case, it's used in the second line, (cons x List-of-X)).

Recursion

Since lists are recursive data structures, we can use recursive procedures to perform operations on them.

In general, a recursive procedure follows the structure

(if <Base Case>  ; determined by the input type
    <Base Case Result>  ; determined by the output type
    (<Combine> <Current Data> <Recursive Call with Remainder Data>))

Breaking things down further, the recursive call typically involves the following steps:

1. Break the data into a "current" piece and a "remainder"
2. Handle the "current" piece according to the function
3. Recursively call your function with the "remainder" of the data
4. Combine the results from 1 and 2, and return this combination

Avoiding infinite loops

It is extremely important that your recursive call uses a smaller version of the original input data. Otherwise, you'll never reach your base case, and the function will recurse forever.

The following function loops forever:

; factorial/broken : number -> number
(define (factorial/broken n)
  (if (= n 0) 1  ; remember that 0! = 1 by definition
      (* n
         (factorial/broken n))))  ; eek

Once we fix our recursive call to operate on (- n 1), it works:

; factorial : number -> number
(define (factorial n)
  (if (= n 0) 1
      (* n
         (factorial (- n 1)))))  ; much better

Base Cases

Here are some common base cases and combinations:

Examples of templates for recursion

These are all very general templates; you will almost never be able to follow them exactly, so memorizing them won't do you much good. However, they do provide examples of the base cases.

Note that the <Base Case Result> and <Combiner> depend on the output type, which is specified as X in all of the examples below.

Lists

; List -> X
(define (recursive-lst-proc lst)
  (if (empty? lst) <Base Case Result>
      (<Combiner> (first lst)
                  (recursive-lst-proc (rest lst)))))

Numbers

; Number -> X
(define (recursive-num-proc n)
  (if (= n 0) <Base Case Result>
      (<Combiner> n
                  (recursive-num-proc (- n 1)))))

Trees

; Tree -> X
(define-struct node (value children))

(define (recursive-tree-proc t)
  (if (empty? t) <Base Case Result>
      (<Combiner> (node-value t)
                  (map recursive-tree-proc (node-children t)))))

Iterative Recursion

Iterative recursion is also called recursion with accumulators (and infrequently in this course, tail recursion).

The main difference between "ordinary" recursion and iterative recursion is that iterative recursion uses an accumulator as an additional input to the function.

This accumulator represents the "partial result" of the computation at the current position in the data. It allows the computer to represent the previously-seen data in a compact manner, by only remembering the "relevant" parts. (What's relevant is determined by the particular task of the function -- here are some examples:)

Here are two version of sum-list, written without and with accumulators.

; sum-list : List-of-Number -> Number
(define (sum-list lon)
  (if (empty? lon)
      0
      (+ (first lon)
         (sum-list (rest lon)))))

; sum-list/iter : List-of-Number -> Number
(define (sum-list/iter lon acc)
  (if (empty? lon)
      acc  ; changed from 0
      (sum-list/iter (rest lon)
                     (+ (first lon) acc)))) ; note that the (+ (first lon) ...) has been moved INSIDE the recursive call

Here's a comparison of how the two functions are evaluated:

; Without accumulator
(sum-list (list 1 2 3 4))

; With accumulator
(sum-list/iter (list 1 2 3 4)
               0)

After one time step:

; Without accumulator
(+ 1
   (sum-list (list 2 3 4)))

; With accumulator
(sum-list/iter (list 2 3 4)
               1)

After another step:

; Without accumulator: notice the "trail" growing...
(+ 1
   (+ 2
      (sum-list (list 3 4))))

; With accumulator: still nice and compact
(sum-list/iter (list 3 4)
               3)

; Without accumulator
(+ 1
   (+ 2
      (+ 3
         (sum-list (list 4)))))

; With accumulator
(sum-list/iter (list 4)
               6)

; Without accumulator
(+ 1
   (+ 2
      (+ 3
         (+ 4
            (sum-list empty)))))

; With accumulator
(sum-list/iter empty
               10)

; Without accumulator
(+ 1
   (+ 2
      (+ 3
         (+ 4
            empty))))

; With accumulator
10

Evidently, iterative recursion is far more efficient than regular recursion. That's because the accumulator is basically a compact encoding of everything the program needs to know about the previously-seen data, so we don't need to remember all the data itself.

Imperative Programming

Imperative programming is a style of programming characterized by providing the computer simple, detailed instructions for everything.

Here are the main imperative functions you should understand:

Do nothing

(void)

Does nothing. If a function doesn't return any values, we say it "returns (void)".

Conditionally do nothing

(when <Condition> <Result>)
(unless <Condition> <Result>)

when executes <Result> if and only if <Condition> is true. unless does the opposite.

Fun fact: the funnest fact.

; (when <Condition> <Result>) is equivalent to
(if <Condition>
    <Result>
    (void))
    
; (unless <Condition> <Result>) is equivalent to
(if <Condition>
    (void)
    <Result>)

Do a sequence of instructions

(begin
  <FunctionCall#1>
  <FunctionCall#2>
  ...
  <ReturnFunctionCall>)

Executes a sequence of function calls, one at a time, and returns the value of the last one.

Mutate variables

(set! <Variable Name> <New Value>)

Note that <Variable Name> must previously have been defined.

Iteratively traverse a list

(for-each proc lst)
; if lst is a List-of-X, then proc must take an input of type X

Just like map, in that it calls proc with each item in order, but does not return the resulting list.

Warning: Remember to use for-each with a proc that performs some kind of mutation (or causes a side effect). If proc just returns a new value, that value will disappear into the void, since for-each doesn't return anything.

(define my-list (list 1 2 3))
(define (doubler n) (* 2 n))

(for-each doubler my-list)

; my-list is still (list 1 2 3)

What you should know

Understand how side effects work, and how to translate functional-style code into its imperative equivalents.

Here's an example: the inimitable sum-list, written imperatively, with and without for-each.

; sum-list/imperative : (listof number) -> number
; sums a list imperatively
(define (sum-list/imperative lon)
  (local [(define sum 0)

          (define remaining lon)

          (define (loop)
            (if
             ; If remaining is an empty list, return sum
             (empty? remaining) sum

             ; Otherwise...
             (begin
               ; First, update the value of sum
               (set! sum (+ sum (first remaining)))
               ; Next, update the remaining list
               (set! remaining (rest remaining))
               ; Finally, repeat
               (loop))))]
    ; Kick off the loop
    (loop)))

; sum-list/for-each : (listof numbers) -> number
; sums a list imperatively
(define (sum-list/for-each lon)
  (local [; Initialize the sum to zero
          (define sum 0)]

    (begin
      ; Loop through the list, adding each item to the sum
      (for-each (lambda (item)
                  (set! sum (+ sum item)))
                lon)

      ; After we're done looping, return the sum
      sum)))

; Using for-each works the same way as before
(check-expect (sum-list/for-each (list 1 2 3))
              (sum-list (list 1 2 3)))

Structs and mutation

Recall that structs have "accessor" functions for each of their fields:

(<Struct Name>-<Field Name> <Instance of Struct>)

(define-struct person (name age))
; name is a string
; age is a number

(define wizard (make-struct "Harry Potter" 17))

(person-name wizard)  ; "Harry Potter"

Just as we can use set! to mutate previously-defined variables, we can mutate the fields of structs.

(set-<Struct Name>-<Field-Name>! <Instance of Struct> <New Field Value>)

; Continuing the above example...

(person-name wizard)  ; "Harry Potter"

(set-person-name! wizard "Ron Weasley")

(person-name wizard)  ; "Ron Weasley"

What else?

Things that might be helpful to brush up on:

• Type signatures and consistency (this will never not be important)
• Grammar rules of Racket
• Local scope (local)
• Basics of how structs work

Ways to evaluate your preparedness:

• Can you do all of the homeworks/tutorials since the last midterm?

  • Not because we're going to pop some wild evolutionary tree question on you, but because they're good applications of the course material (and good examples of how we write questions!)

• Can you write your own implementations of map, filter, foldl, ormap, etc. using both recursion and imperative iteration?