As usual, this is not a comprehensive review sheet, nor is it "official."
Accessing parts of a list with
Recall that given any list, we can use
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)
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.
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:
(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)).
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:
- Break the data into a "current" piece and a "remainder"
- Handle the "current" piece according to the function
- Recursively call your function with the "remainder" of the data
- 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
Here are some common base cases and combinations:
||Arithmetic operations (usually
||N/A (usually a return type)||
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.
; List -> X (define (recursive-lst-proc lst) (if (empty? lst) <Base Case Result> (<Combiner> (first lst) (recursive-lst-proc (rest lst)))))
; Number -> X (define (recursive-num-proc n) (if (= n 0) <Base Case Result> (<Combiner> n (recursive-num-proc (- n 1)))))
; 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 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:)
|List of numbers||Sum||Partial sum of all numbers seen so far|
|List of strings||Longest string||Longest string seen so far|
|List of numbers||List of all odd numbers||List of all odd numbers seen so far|
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 is a style of programming characterized by providing the computer simple, detailed instructions for everything.
|Functions almost always take inputs||Functions may not take any inputs|
|Functions always have return values||Functions may not have any return value (i.e. they may return
|Functions always return the same output for a particular input||Functions are allowed to return whatever they want, or nothing at all|
|Use recursion to traverse structures||Use iteration to traverse structures|
|Variables never change values (they are "immutable")||Variables can change values (they are "mutable")|
|Functions never affect things outside their scope||Functions have "side effects"|
Here are the main imperative functions you should understand:
Does nothing. If a function doesn't return any values, we say it "returns
Conditionally do nothing
(when <Condition> <Result>) (unless <Condition> <Result>)
<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.
(set! <Variable Name> <New Value>)
<Variable Name> must previously have been
Iteratively traverse a list
(for-each proc lst) ; if lst is a List-of-X, then proc must take an input of type X
map, in that it calls
proc with each item in order, but does not return the resulting list.
Warning: Remember to use
procthat performs some kind of mutation (or causes a side effect). If
procjust returns a new value, that value will disappear into the void, since
for-eachdoesn'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
; 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"
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 (
- 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
ormap, etc. using both recursion and imperative iteration?