Scheme & Functional Programming Cheat Sheet

Basic Syntax & Notation

Prefix Notation

;; Infix vs Prefix ;; Infix: 2 + 3 * 4 ;; Prefix: (+ 2 (* 3 4)) ;; All operations are functions (+ 1 2 3 4) ;; → 10 (* 2 3 4) ;; → 24 (- 10 3) ;; → 7 (/ 20 4) ;; → 5

Basic Forms

;; Numbers 42, 3.14, -17, 1/3 ;; Booleans #t, #f ;; Characters #\a, #\b, #\space, #\newline ;; Strings "Hello World" ;; Symbols 'hello, 'world, '+

Core Procedures

Procedure	Description	Example
define	Create variables/procedures	(define x 5)
if	Conditional expression	(if (> x 0) "pos" "neg")
cond	Multiple conditions	(cond [(> x 0) "pos"] [else "neg"])
and	Logical AND	(and #t #f) → #f
or	Logical OR	(or #t #f) → #t
not	Logical NOT	(not #t) → #f
abs	Absolute value	(abs -5) → 5
odd?	Check if odd	(odd? 3) → #t
even?	Check if even	(even? 4) → #t

Defining Procedures

;; Basic procedure definition (define (procedure-name param1 param2) body-expression) ;; Example: Add procedure (define (add x y) (+ x y)) ;; Usage (add 5 3) ;; → 8 ;; Lambda (anonymous functions) (lambda (x y) (+ x y)) ((lambda (x y) (+ x y)) 5 3) ;; → 8

The Fantastic Recursive Approach

Four Steps to Recursive Solutions:

Size-n Problem: What are we trying to solve?
Stopping Conditions: When do we stop recursing?
Size-m Problems: What smaller problems do we solve?
Construction: How do we build the solution from smaller parts?

Factorial Example

(define (factorial n) ;; 1. Size-n problem: factorial of n (if (<= n 1) ;; 2. Stopping condition: n <= 1, return 1 1 ;; 3. Size-m problem: factorial of (n-1) ;; 4. Construction: n * factorial(n-1) (* n (factorial (- n 1))))) ;; Test cases (factorial 5) ;; → 120 (factorial 0) ;; → 1

Fibonacci Example

(define (fib n) ;; 1. Size-n problem: nth Fibonacci number (cond ;; 2. Stopping conditions [(<= n 0) 0] [(= n 1) 1] ;; 3&4. Size-m problems and construction [else (+ (fib (- n 1)) (fib (- n 2)))])) ;; Test cases (fib 0) ;; → 0 (fib 9) ;; → 34

Data Types & Predicates

Type	Predicate	Example
Number	number?	(number? 42) → #t
String	string?	(string? "hi") → #t
Symbol	symbol?	(symbol? 'x) → #t
Character	char?	(char? #\a) → #t
Boolean	boolean?	(boolean? #t) → #t
List	list?	(list? '(1 2 3)) → #t
Null	null?	(null? '()) → #t

Input/Output

;; Reading input (read) ;; Read from keyboard ;; Example: Read and square (define (read-for-square) (let ([input (read)]) (* input input))) ;; Multiple reads (* (read) (read)) ;; Multiply two inputs

Note: Avoid display, write, and begin forms in pure functional code

Common Recursive Patterns

Linear Recursion

;; Sum of odd numbers up to max (define (sum-odds max) (cond [(<= max 0) 0] [(odd? max) (+ max (sum-odds (- max 2)))] [else (sum-odds (- max 1))]))

Tree Recursion

;; Already shown with Fibonacci ;; Two recursive calls create tree structure

Tail Recursion (with helpers)

(define (factorial-tail n) (define (fact-helper n acc) (if (<= n 1) acc (fact-helper (- n 1) (* n acc)))) (fact-helper n 1))

Conditional Expressions

;; Simple if (if condition true-expr false-expr) ;; Multiple conditions with cond (cond [condition1 expression1] [condition2 expression2] [else default-expression]) ;; Example: Absolute value (define (my-abs x) (if (< x 0) (- x) x))

Working Without Multiplication

;; Square using only addition (define (square n) (define (square-helper n count acc) (if (= count (abs n)) acc (square-helper n (+ count 1) (+ acc (+ (abs n) (abs n) -1))))) (if (= n 0) 0 (square-helper n 0 0))) ;; Using the pattern: n² = 1+3+5+...+(2n-1)

Functional Programming Principles

Core Concepts

Immutability: Values don't change
Pure Functions: No side effects
First-Class Functions: Functions as values
Recursion: Instead of loops
Expression-Based: Everything returns a value

Benefits

Easier to reason about
Natural parallelization
Fewer bugs
Mathematical elegance
Composability

Glossary of Terms

Term	Definition
Atom	Indivisible data element (number, symbol, etc.)
Expression	Any valid Scheme code that evaluates to a value
Form	Syntactic structure in Scheme
Lambda	Anonymous function
Predicate	Function that returns true/false
Procedure	Named function
S-Expression	Symbolic expression (atoms or lists)
Tail Recursion	Recursive call is the last operation
Higher-Order Function	Function that takes/returns functions
Closure	Function with access to outer scope
Base Case	Stopping condition in recursion
Recursive Case	Case that calls itself
Arity	Number of arguments a function takes
Side Effect	Observable change outside function
Referential Transparency	Expression can be replaced by its value

DrRacket Tips

Language: Select "Determine language from source"
Debugging: Use stepper for recursive visualization
Testing: Put test cases at bottom of file
Comments: Use ;; for line comments
Indentation: DrRacket auto-indents properly
Parentheses: Use Ctrl+] to match brackets

Common Mistakes to Avoid

Missing parentheses in function calls
Using assignment instead of functional approach
Forgetting base cases in recursion
Mixing infix and prefix notation
Using display/write in pure functions
Not handling edge cases (negative numbers, zero)