CS 135: Designing Functional Programs

Estimated study time: 23 minutes

Table of contents

Design Recipes

The Design Recipe (for every function). Follow these steps in order:

Purpose: Describe what the function computes, using parameter names.
Contract: Specify parameter types and return type (e.g., Num Num -> Num).
Examples: Write check-expect tests illustrating typical use.
Definition: Write the header and body.
Tests: Additional directed tests (boundary cases, edge cases).

Execution order: draft purpose, write examples (by hand then code), write header and contract, finalize purpose with parameter names, write body, write tests.

A complete design recipe example:

;; (sum-of-squares p1 p2) produces the sum of
;;   the squares of p1 and p2
;; sum-of-squares: Num Num -> Num
;; Examples:
(check-expect (sum-of-squares 3 4) 25)
(check-expect (sum-of-squares 0 2.5) 6.25)

(define (sum-of-squares p1 p2)
  (+ (* p1 p1) (* p2 p2)))

;; Tests:
(check-expect (sum-of-squares 0 0) 0)
(check-expect (sum-of-squares -2 7) 53)

Design Recipe for Compound Data. Do once per new structure type:

Data analysis and definition: Define new structures, write data definitions.
Template: Create once per structure type, used for functions consuming that type.

Then do the standard per-function design recipe (purpose, contract, examples, definition, tests).

Design Recipe for Self-Referential Data. Do once per self-referential type:

Data definition: Must contain at least one base case (non-self-referential clause).
Template: A cond with one clause per data definition clause. Self-referential clauses lead to recursive expressions; base case clauses do not.

Contract type abbreviations: Num (any number), Int (integer), Nat (natural number including 0), Bool (boolean), Sym (symbol), Str (string), Char (character), Any (any value). Structure names (e.g., Posn, SR) are used directly. Lists use (listof X) notation.

Testing constructs:

(check-expect (f 3 4) 25)           ;; exact equality
(check-within (sqrt 2) 1.414 .001)  ;; approximate equality
(check-error (/ 1 0) "/: division by zero")  ;; expected error

Black-box tests are written before the body (based on the purpose). White-box tests are written after, to exercise specific code paths (e.g., each branch of a cond).

Racket Basics

Syntax

Racket uses prefix notation with parentheses for function application. The function name comes first inside the parentheses, followed by arguments separated by spaces.

(+ 3 5)          ;; => 8
(* (- 6 4) (+ 3 2))  ;; => 10
(/ (- 6 4) (+ 5 7))  ;; => 1/6

Parentheses signal function application (or special forms). Extra parentheses are harmful – do not add unnecessary ones.

A Racket program is a sequence of definitions and expressions. Expressions are evaluated using substitution to produce values.

Data Types

Numbers: Integers are unbounded. Rationals are exact. Inexact numbers are flagged with #i (e.g., (sqrt 2) produces #i1.4142...).

Booleans: true and false. (Standard Racket uses #t and #f.)

Symbols: Written with a leading quote: 'blue, 'red. Compared with symbol=?. Cannot contain spaces or special characters.

Strings: Written in double quotes: "hello". Compound data (sequence of characters). Useful functions: string-append, string-length, string<?, string->list, list->string.

Characters: Written as #\a, #\newline, etc. Compared with char=?. Predicates: char-alphabetic?, char-numeric?, char-whitespace?.

Special Forms

define – binds names to values or defines functions:

(define k 3)                  ;; constant definition
(define p (* k k))            ;; expression evaluated, then bound
(define (f x) (* x x))       ;; function definition
(define (g x y) (+ x y))     ;; multi-parameter function

cond – conditional expression:

(cond
  [question1 answer1]
  [question2 answer2]
  ...
  [else default-answer])

Questions are evaluated top-to-bottom. As soon as one is true, only that answer is evaluated. The else clause catches everything remaining.

and, or – short-circuit Boolean connectives (special forms, not functions):

(and (>= x 0) (< x 10))   ;; true when both are true
(or (= x 0) (> x 5))      ;; true when at least one is true
(not false)                 ;; true (not is a regular function)

and evaluates left to right, stopping at the first false. or stops at the first true. This enables safe guarding:

(and (not (= x 0)) (<= (/ y x) c))  ;; never divides by zero

Predicates

A predicate is a function producing a Boolean. Built-in examples: even?, odd?, negative?, zero?, number?, symbol?, string?, empty?, cons?.

Comparisons: =, <, >, <=, >= for numbers. symbol=? for symbols. string=? for strings. equal? for general structural equality (works on most types).

Functions and the Substitution Model

→

(+ 3 5) [sub x=3, y=5]

→

user-defined callsubstitute paramsvalue

(square (+ 1 2)) → (square 3) → (* 3 3) → 9Rule: evaluate leftmost innermost subexpr first (applicative order)Stepper rule 5: args are fully evaluated before applying a functionConstant lookup: name → its defined value (rule 4)

Function Definition. A function definition consists of: a name, a list of parameters, and a single body expression. The body typically uses the parameters together with built-in and user-defined functions.

(define (g x y) (+ x y))
;; (g 3 5) => (+ 3 5) => 8

Parameter names are meaningful only within the body. The two definitions below define the same function:

(define (f x y) (+ x y))
(define (f a b) (+ a b))

Substitution Model of Evaluation. To evaluate an expression:

Values are already fully evaluated.
For a built-in function application \((f\; v_1 \ldots v_n)\), replace with the computed result.
For a user-defined function application \((f\; v_1 \ldots v_n)\) where \((\text{define } (f\; x_1 \ldots x_n)\; \text{exp})\), replace with exp where each \(x_i\) is substituted by \(v_i\).
For a constant reference id, replace with its bound value.
Arguments must be fully evaluated to values before a function is applied.
When there is a choice, evaluate the leftmost eligible subexpression first.

Substitution rules for cond:

(cond [false exp] ...) simplifies to (cond ...)
(cond [true exp] ...) simplifies to exp
(cond [else exp]) simplifies to exp

Substitution rules for and/or:

(and false ...) simplifies to false; (and true ...) simplifies to (and ...); (and) simplifies to true
(or true ...) simplifies to true; (or false ...) simplifies to (or ...); (or) simplifies to false

A step-by-step reduction according to these rules is called a trace.

(define (term x y) (* x (sqr y)))
(term (- 3 1) (+ 1 2))
;; => (term 2 (+ 1 2))
;; => (term 2 3)
;; => (* 2 (sqr 3))
;; => (* 2 9)
;; => 18

Structures

Structures bundle several values into one compound datum.

(define-struct posn (x y))
;; Creates: make-posn (constructor), posn-x, posn-y (selectors), posn? (predicate)

Substitution rules for structures:

(posn-x (make-posn v1 v2)) simplifies to v1
(posn? (make-posn v1 v2)) simplifies to true
(posn? V) simplifies to false for any value V not a posn

Data definitions document the types of fields:

;; A Posn is a (make-posn Num Num)

Templates for structures select every field:

(define (my-posn-fn p)
  (... (posn-x p) ... (posn-y p) ...))

Mixed data uses cond with type predicates:

;; A MmInfo is one of:
;; - an Mp3Info
;; - a MovieInfo
(define (my-mminfo-fn info)
  (cond [(mp3info? info) ...]
        [(movieinfo? info) ...]))

In contracts, use (anyof Type1 Type2) for mixed types.

Lists

List Data Definition. A list is one of:

empty
(cons value list)

This is a recursive definition with a base case (empty) and a recursive case (cons).

Core list operations:

Operation	Purpose	Contract
`empty`	The empty list value	–
`cons`	Prepend an item to a list	`Any (listof Any) -> (listof Any)`
`first`	First element of a nonempty list	`(listof Any) -> Any`
`rest`	All but first element	`(listof Any) -> (listof Any)`
`empty?`	Test if list is empty	`Any -> Bool`
`cons?`	Test if value is a cons	`Any -> Bool`

Substitution rules: (first (cons a b)) simplifies to a; (rest (cons a b)) simplifies to b; (empty? empty) simplifies to true.

The list template (structural recursion on lists):

(define (my-list-fn lst)
  (cond [(empty? lst) ...]
        [else (... (first lst) ...
                   (my-list-fn (rest lst)) ...)]))

Example – counting elements:

(define (my-length lst)
  (cond [(empty? lst) 0]
        [else (+ 1 (my-length (rest lst)))]))

Example – producing a new list:

(define (negate-list lon)
  (cond [(empty? lon) empty]
        [else (cons (- (first lon))
                    (negate-list (rest lon)))]))

List Abbreviations

(list 1 2 3)       ;; same as (cons 1 (cons 2 (cons 3 empty)))
'(red blue green)  ;; quoted list of symbols
'(1 2 3)           ;; quoted list of numbers
'()                ;; empty

second, third, …, eighth are shorthand for nested first/rest combinations.

Insertion Sort

(define (sort lon)
  (cond [(empty? lon) empty]
        [else (insert (first lon) (sort (rest lon)))]))

(define (insert n slon)
  (cond [(empty? slon) (cons n empty)]
        [(<= n (first slon)) (cons n slon)]
        [else (cons (first slon) (insert n (rest slon)))]))

Association Lists (Dictionaries)

;; An AL is one of:
;; - empty
;; - (cons (list Num Str) AL)

(define (lookup-al k alst)
  (cond [(empty? alst) false]
        [(equal? k (first (first alst))) (second (first alst))]
        [else (lookup-al k (rest alst))]))

Recursion

Structural Recursion

Pure Structural Recursion. All arguments to recursive applications are either unchanged or one step closer to a base case according to the data definition. The form of the code mirrors the form of the data definition.

Natural Number Recursion

;; A Nat is one of:
;; - 0
;; - (add1 Nat)

(define (my-nat-fn n)
  (cond [(zero? n) ...]
        [else (... n ... (my-nat-fn (sub1 n)) ...)]))

Example – countdown:

(define (countdown n)
  (cond [(zero? n) (cons 0 empty)]
        [else (cons n (countdown (sub1 n)))]))
;; (countdown 3) => (list 3 2 1 0)

Counting Up

(define (countup-to n b)
  (cond [(= n b) (cons b empty)]
        [else (cons n (countup-to (add1 n) b))]))
;; (countup-to 6 8) => (list 6 7 8)

Processing Two Lists

Case 1 – One list only (other parameter along for the ride):

(define (my-append lst1 lst2)
  (cond [(empty? lst1) lst2]
        [else (cons (first lst1)
                    (my-append (rest lst1) lst2))]))

Case 2 – Lockstep (same length, consumed at same rate):

(define (dot-product lon1 lon2)
  (cond [(empty? lon1) 0]
        [else (+ (* (first lon1) (first lon2))
                 (dot-product (rest lon1) (rest lon2)))]))

Case 3 – Different rates (four cases for empty/nonempty combinations):

(define (merge lon1 lon2)
  (cond [(empty? lon1) lon2]
        [(empty? lon2) lon1]
        [(< (first lon1) (first lon2))
         (cons (first lon1) (merge (rest lon1) lon2))]
        [else (cons (first lon2) (merge lon1 (rest lon2)))]))

Trees

Binary Trees

(define-struct node (key val left right))
;; A Node is a (make-node Num Str BT BT)
;; A binary tree (BT) is one of:
;; - empty
;; - a Node

Template:

(define (my-bt-fn tree)
  (cond [(empty? tree) ...]
        [else (... (node-key tree) ...
                   (node-val tree) ...
                   (my-bt-fn (node-left tree)) ...
                   (my-bt-fn (node-right tree)) ...)]))

Binary Search Trees (BSTs)

BST Ordering Property. For any node with key \(k\):

Every key in the left subtree is less than \(k\).
Every key in the right subtree is greater than \(k\).

Searching a BST – only one recursive call needed:

(define (search-bst n t)
  (cond [(empty? t) false]
        [(= n (node-key t)) (node-val t)]
        [(< n (node-key t)) (search-bst n (node-left t))]
        [(> n (node-key t)) (search-bst n (node-right t))]))

Adding to a BST:

(define (add-to-bst k v t)
  (cond [(empty? t) (make-node k v empty empty)]
        [(= k (node-key t)) (make-node k v (node-left t) (node-right t))]
        [(< k (node-key t))
         (make-node (node-key t) (node-val t)
                    (add-to-bst k v (node-left t)) (node-right t))]
        [else
         (make-node (node-key t) (node-val t)
                    (node-left t) (add-to-bst k v (node-right t)))]))

General Trees and Mutual Recursion

When internal nodes can have any number of children, use a list of children. This leads to mutual recursion between a function on the tree node and a function on the list of children.

(define-struct ainode (op args))
;; An AExp is one of:
;; - a Num
;; - (make-ainode (anyof '* '+) (listof AExp))

(define (eval-aexp ex)
  (cond [(number? ex) ex]
        [else (apply-op (ainode-op ex) (ainode-args ex))]))

(define (apply-op f exlist)
  (cond [(and (empty? exlist) (symbol=? f '*)) 1]
        [(and (empty? exlist) (symbol=? f '+)) 0]
        [(symbol=? f '*)
         (* (eval-aexp (first exlist)) (apply-op f (rest exlist)))]
        [(symbol=? f '+)
         (+ (eval-aexp (first exlist)) (apply-op f (rest exlist)))]))

Nested Lists

;; A Nested-List-Num is one of:
;; - empty
;; - (cons Num Nested-List-Num)
;; - (cons Nested-List-Num Nested-List-Num)

(define (flatten lst)
  (cond [(empty? lst) empty]
        [(number? (first lst))
         (cons (first lst) (flatten (rest lst)))]
        [else (append (flatten (first lst))
                      (flatten (rest lst)))]))

Higher-Order Functions

map sqr:1 4 9 16 25

filter odd?:1 3 5

foldr + 0:15

In the Intermediate language, functions are first-class values: they can be passed as arguments, returned as results, bound to identifiers, and placed in data structures.

filter

Removes elements that do not satisfy a predicate:

;; filter: (X -> Bool) (listof X) -> (listof X)
(define (my-filter pred? lst)
  (cond [(empty? lst) empty]
        [(pred? (first lst))
         (cons (first lst) (my-filter pred? (rest lst)))]
        [else (my-filter pred? (rest lst))]))

(filter odd? (list 1 2 3 4 5))  ;; => (list 1 3 5)

map

Transforms each element of a list:

;; map: (X -> Y) (listof X) -> (listof Y)
(define (my-map f lst)
  (cond [(empty? lst) empty]
        [else (cons (f (first lst))
                    (my-map f (rest lst)))]))

(map sqr (list 1 2 3))  ;; => (list 1 4 9)

foldr (fold right)

Abstracts the general list recursion pattern:

;; foldr: (X Y -> Y) Y (listof X) -> Y
(define (my-foldr combine base lst)
  (cond [(empty? lst) base]
        [else (combine (first lst)
                       (my-foldr combine base (rest lst)))]))

foldr Expansion. The application (foldr f b (list x1 x2 ... xn)) computes (f x1 (f x2 (... (f xn b) ...))).

(foldr + 0 (list 3 6 5))        ;; => 14    (sum)
(foldr * 1 (list 2 3 4))        ;; => 24    (product)
(foldr cons empty (list 1 2 3)) ;; => (list 1 2 3) (identity)

Implementing map and filter with foldr:

(define (my-map f lst)
  (foldr (lambda (x y) (cons (f x) y)) empty lst))

(define (my-filter pred? lst)
  (foldr (lambda (x y) (if (pred? x) (cons x y) y)) empty lst))

foldl (fold left)

Abstracts accumulative recursion on lists:

;; foldl: (X Y -> Y) Y (listof X) -> Y
(define (my-foldl combine base lst0)
  (local [(define (foldl-acc lst acc)
            (cond [(empty? lst) acc]
                  [else (foldl-acc (rest lst)
                                   (combine (first lst) acc))]))]
    (foldl-acc lst0 base)))

(foldl f b (list x1 x2 ... xn)) computes (f xn (... (f x2 (f x1 b)) ...)).

(define (sum-list lon) (foldl + 0 lon))
(define (my-reverse lst) (foldl cons empty lst))

build-list

Constructs a list from a function applied to indices:

;; build-list: Nat (Nat -> X) -> (listof X)
(build-list 5 sqr)  ;; => (list 0 1 4 9 16)
(build-list 4 add1) ;; => (list 1 2 3 4)

lambda (Anonymous Functions)

(lambda (x) (* x x))  ;; anonymous squaring function

(filter (lambda (x) (> x 3)) (list 1 5 2 7))  ;; => (list 5 7)
(map (lambda (x) (+ x 1)) (list 10 20 30))    ;; => (list 11 21 31)

Lambda Substitution Rule. ((lambda (x1 ... xn) exp) v1 ... vn) simplifies to exp with each \(x_i\) replaced by \(v_i\).

Internally, (define (f x) body) is equivalent to (define f (lambda (x) body)).

Parametric Contracts

Use type variables (like X, Y) to express relationships:

;; filter: (X -> Bool) (listof X) -> (listof X)
;; map:    (X -> Y) (listof X) -> (listof Y)
;; foldr:  (X Y -> Y) Y (listof X) -> Y
;; foldl:  (X Y -> Y) Y (listof X) -> Y

Local Definitions

The local special form introduces definitions visible only within a body expression.

(local [(define s (/ (+ a b c) 2))]
  (sqrt (* s (- s a) (- s b) (- s c))))

Semantics of local

Evaluation of (local [(define x1 exp1) ... (define xn expn)] bodyexp):

Replace each xi with a fresh unique name throughout the local expression.
Lift the renamed definitions to the top level.
Replace (local [] bodyexp') with bodyexp'.

This is a single substitution step.

Uses of local

Naming common subexpressions (avoid recomputation):

(define (max-list lon)
  (cond [(empty? (rest lon)) (first lon)]
        [else
         (local [(define max-rest (max-list (rest lon)))]
           (cond [(> (first lon) max-rest) (first lon)]
                 [else max-rest]))]))

Encapsulation – hiding helper functions:

(define (isort lon)
  (local [(define (insert n slon)
            (cond [(empty? slon) (cons n empty)]
                  [(<= n (first slon)) (cons n slon)]
                  [else (cons (first slon) (insert n (rest slon)))]))]
    (cond [(empty? lon) empty]
          [else (insert (first lon) (isort (rest lon)))])))

Eliminating “along for the ride” parameters:

(define (countup-to n)
  (local [(define (countup-from m)
            (cond [(> m n) empty]
                  [else (cons m (countup-from (add1 m)))]))]
    (countup-from 0)))

Scope Rules

The binding occurrence of a name is its use in a define or as a formal parameter.
The lexical scope of a binding is the region where it has effect.
A local definition can shadow an outer definition of the same name.
Global scope is the scope of top-level definitions.

Accumulators

Accumulative Recursion. Arguments to recursive calls include one or more accumulators that carry partial results. A wrapper function sets the initial accumulator value.

Example – reversing a list:

(define (my-reverse lst)
  (local [(define (rev/acc lst acc)
            (cond [(empty? lst) acc]
                  [else (rev/acc (rest lst)
                                 (cons (first lst) acc))]))]
    (rev/acc lst empty)))

Example – summing a list:

(define (sum-list lon)
  (local [(define (sum/acc lst sofar)
            (cond [(empty? lst) sofar]
                  [else (sum/acc (rest lst)
                                 (+ (first lst) sofar))]))]
    (sum/acc lon 0)))

The accumulator invariant expresses the relationship between the original arguments and the accumulator at each recursive call. For sum-list: the sum of lon equals sofar plus the sum of lst.

Generative Recursion

Generative Recursion. The recursive cases are generated by computation on the problem, not derived from a data definition. The base cases also do not follow from a data definition. Requires correctness arguments and termination proofs.

Termination

For structural recursion, arguments always get smaller toward a base case, so termination is guaranteed.

For generative recursion, one must identify a measure of progress that decreases with each recursive call and is bounded below. If no such measure exists, the function may not terminate.

Quicksort

A divide-and-conquer sorting algorithm:

(define (quick-sort lon)
  (cond [(empty? lon) empty]
        [else
         (local [(define pivot (first lon))
                 (define less (filter (lambda (x) (< x pivot)) (rest lon)))
                 (define greater (filter (lambda (x) (>= x pivot)) (rest lon)))]
           (append (quick-sort less)
                   (list pivot)
                   (quick-sort greater)))]))

Termination: Both less and greater have strictly fewer elements than the original list (neither contains the pivot). Worst case (already sorted): \(O(n^2)\). Best/average case: \(O(n \log n)\).

Mergesort (via BST)

An alternative approach: insert elements into a BST, then perform an inorder traversal:

(define (bst-inorder t)
  (cond [(empty? t) empty]
        [else (append (bst-inorder (node-left t))
                      (list (node-key t))
                      (bst-inorder (node-right t)))]))

GCD (Euclidean Algorithm)

(define (euclid-gcd n m)
  (cond [(zero? m) n]
        [else (euclid-gcd m (remainder n m))]))

Termination: the second argument strictly decreases (since \(m > n \bmod m\)) and is bounded below by 0.

String Processing: Tokenizing

Generative recursion views a character list as a sequence of tokens rather than individual characters:

(define (list->lines loc)
  (cond [(empty? loc) empty]
        [else (cons (first-line loc)
                    (list->lines (rest-of-lines loc)))]))

(define (first-line loc)
  (cond [(empty? loc) empty]
        [(char=? (first loc) #\newline) empty]
        [else (cons (first loc) (first-line (rest loc)))]))

(define (rest-of-lines loc)
  (cond [(empty? loc) empty]
        [(char=? (first loc) #\newline) (rest loc)]
        [else (rest-of-lines (rest loc))]))

Graphs

Directed Graph. A collection of nodes and directed edges (ordered pairs of nodes). An edge \((v, w)\) means \(w\) is an out-neighbour of \(v\). A path is a sequence of nodes connected by edges. A cycle is a path where the first and last nodes are the same. A DAG is a directed acyclic graph.

Adjacency List Representation

;; A Node is a Sym
;; A Graph is a (listof (list Node (listof Node)))

(define G '((A (C D E)) (B (E J)) (C ()) (D (F J))
            (E (K)) (F (K H)) (H ()) (J (H)) (K ())))

Neighbours function:

(define (neighbours v G)
  (cond [(empty? G) (error "vertex not in graph")]
        [(symbol=? v (first (first G))) (second (first G))]
        [else (neighbours v (rest G))]))

Backtracking (Route Finding)

Uses generative recursion with mutual recursion between find-route and find-route/list:

(define (find-route orig dest G)
  (cond [(symbol=? orig dest) (list orig)]
        [else (local [(define nbrs (neighbours orig G))
                      (define route (find-route/list nbrs dest G))]
                (cond [(false? route) false]
                      [else (cons orig route)]))]))

(define (find-route/list los dest G)
  (cond [(empty? los) false]
        [else (local [(define route (find-route (first los) dest G))]
                (cond [(false? route)
                       (find-route/list (rest los) dest G)]
                      [else route]))]))

Warning: This does not terminate on graphs with cycles.

Handling Cycles with an Accumulator

Add a visited list to avoid revisiting nodes:

(define (find-route orig dest G)
  (local [(define (find-route/acc orig visited)
            (cond [(symbol=? orig dest) (list orig)]
                  [else
                   (local [(define nbrs (neighbours orig G))
                           (define route
                             (find-route/list nbrs visited))]
                     (cond [(false? route) false]
                           [else (cons orig route)]))]))
          (define (find-route/list los visited)
            (cond [(empty? los) false]
                  [(member? (first los) visited)
                   (find-route/list (rest los) visited)]
                  [else
                   (local [(define route
                             (find-route/acc (first los)
                                             (cons (first los) visited)))]
                     (cond [(false? route)
                            (find-route/list (rest los) visited)]
                           [else route]))]))]
    (find-route/acc orig (list orig))))

The accumulator ensures each node is visited at most once, guaranteeing termination even with cycles.

Algorithm Efficiency

Comparing Recursion Types

Type	Arguments in recursive calls	Template-driven?
Pure structural	Unchanged or one step closer to base case	Yes
Accumulative	Same as structural, plus accumulator(s) with partial answers	Partially
Generative	Freely computed at each step	No

Efficiency Observations

Insertion sort: Each element is inserted into its correct position in a growing sorted list. Worst case: \(O(n^2)\) comparisons.

Quicksort: Divides list around a pivot. Average case: \(O(n \log n)\). Worst case (sorted input): \(O(n^2)\).

BST search: In a balanced BST, search takes time proportional to the height, which is \(O(\log n)\) for \(n\) nodes. An unbalanced BST degenerates to a sorted list with \(O(n)\) search.

max-list pitfall: A naive version with two recursive calls on (rest lon) has exponential running time \(O(2^n)\). Using local to cache the result or using an accumulator reduces this to \(O(n)\).

Graph route-finding: With the visited accumulator, find-route/acc is applied at most \(n\) times (once per node). Total work is roughly proportional to \(n(n + m)\) where \(n\) is the number of nodes and \(m\) is the number of edges.

Key Complexity Classes

Notation	Name	Example
\(O(1)\)	Constant	Accessing a structure field
\(O(\log n)\)	Logarithmic	Balanced BST search
\(O(n)\)	Linear	Scanning a list
\(O(n \log n)\)	Linearithmic	Quicksort (average), mergesort
\(O(n^2)\)	Quadratic	Insertion sort, naive nested loops
\(O(2^n)\)	Exponential	Naive max-list with double recursion

Summary of Language Levels

Feature	Beginning Student	Intermediate Student	Intermediate + Lambda
`define`, `cond`, `define-struct`	Yes	Yes	Yes
`local`	No	Yes	Yes
`lambda`	No	No	Yes
Functions as values	No	No	Yes
`map`, `filter`, `foldr`, `foldl`	No	No	Yes
`list` abbreviation	With List Abbrev.	Yes	Yes

Quick Reference: Built-in Functions

Arithmetic

+, -, *, /, sqr, sqrt, expt, abs, max, min, remainder, quotient, modulo, add1, sub1, zero?, even?, odd?, positive?, negative?

Comparison

=, <, >, <=, >=, equal?, symbol=?, string=?, char=?

Boolean

and, or, not, boolean?

List

cons, first, rest, empty?, cons?, list, length, append, reverse, member?, map, filter, foldr, foldl, build-list, sort, second … eighth

String/Character

string-length, string-append, string->list, list->string, string<?, substring, string-ref, char-alphabetic?, char-numeric?, char-whitespace?, char-upcase, char-downcase

Type Predicates

number?, integer?, symbol?, string?, char?, boolean?, empty?, cons?, list?, procedure?

Testing

check-expect, check-within, check-error