Functional Programming in Lisp
Functional Programming: Functions are first-class citizens, can be passed around like data
Prefix Notation: Operator comes first: (+ 1 2) instead of 1 + 2
S-Expressions: Everything is a list in parentheses
Immutability: Data doesn't change; you create new data instead
Recursion: Primary way to loop and iterate
; Comments start with semicolon
; Numbers
42
3.14
-17
2/3 ; Rational number
; Booleans
#t ; true
#f ; false
; Strings
"hello world"
"CSE 240"
; Symbols (like atoms in Prolog)
'apple
'foo
'x
; Lists
'(1 2 3 4)
'(a b c)
'() ; empty list; Arithmetic - operator comes first
(+ 2 3) ; => 5
(- 10 4) ; => 6
(* 5 6) ; => 30
(/ 10 3) ; => 10/3 or 3.333...
(quotient 10 3) ; => 3 (integer division)
(remainder 10 3) ; => 1
(expt 2 8) ; => 256 (2^8)
; Multiple arguments
(+ 1 2 3 4 5) ; => 15
(* 2 3 4) ; => 24
; Nested operations
(+ (* 2 3) (- 10 4)) ; => 6 + 6 = 12
(/ (+ 8 4) (- 6 3)) ; => 12 / 3 = 4(= 5 5) ; => #t (numbers only)
(< 3 5) ; => #t
(> 10 4) ; => #t
(<= 5 5) ; => #t
(>= 8 3) ; => #t
; General equality
(eq? 'a 'a) ; => #t (pointer equality)
(eqv? 5 5) ; => #t (value equality)
(equal? '(1 2) '(1 2)) ; => #t (structural equality)
; Type predicates
(number? 42) ; => #t
(string? "hello") ; => #t
(list? '(1 2 3)) ; => #t
(null? '()) ; => #t
(pair? '(1 . 2)) ; => #t; Define a variable
(define x 10)
(define name "Bob")
(define pi 3.14159)
; Using variables
(+ x 5) ; => 15
(* pi 2) ; => 6.28318; Basic function definition
(define (square x)
(* x x))
(square 5) ; => 25
; Multiple parameters
(define (add-three a b c)
(+ a b c))
(add-three 1 2 3) ; => 6
; Function with multiple expressions (last one is returned)
(define (greet name)
(display "Hello, ")
(display name)
(newline)
"Done!") ; This is returned
; Recursive function
(define (factorial n)
(if (<= n 1)
1
(* n (factorial (- n 1)))))
(factorial 5) ; => 120; Lambda creates unnamed functions
(lambda (x) (* x x))
; Using lambda directly
((lambda (x) (* x x)) 5) ; => 25
; Lambda with multiple parameters
((lambda (x y) (+ x y)) 3 4) ; => 7
; Storing lambda in a variable
(define square (lambda (x) (* x x)))
(square 6) ; => 36
; Lambda in higher-order functions
(map (lambda (x) (* x 2)) '(1 2 3 4)) ; => (2 4 6 8); Syntax: (if condition then-expr else-expr)
(if (> 5 3)
"yes"
"no") ; => "yes"
(define (abs x)
(if (< x 0)
(- x)
x))
(abs -5) ; => 5
(abs 3) ; => 3
; Nested if
(define (sign x)
(if (> x 0)
"positive"
(if (< x 0)
"negative"
"zero"))); cond is like switch/case - cleaner for multiple conditions
(define (grade score)
(cond
((>= score 90) 'A)
((>= score 80) 'B)
((>= score 70) 'C)
((>= score 60) 'D)
(else 'F)))
(grade 85) ; => B
; Another example
(define (describe-number n)
(cond
((< n 0) "negative")
((= n 0) "zero")
((< n 10) "small positive")
((< n 100) "medium positive")
(else "large positive")))
(describe-number 42) ; => "medium positive"; and - returns #f if any are false
(and #t #t #t) ; => #t
(and #t #f #t) ; => #f
; or - returns #t if any are true
(or #f #f #t) ; => #t
(or #f #f #f) ; => #f
; not - negation
(not #t) ; => #f
(not #f) ; => #t
; Practical example
(define (in-range? x low high)
(and (>= x low) (<= x high)))
(in-range? 5 1 10) ; => #t
(in-range? 15 1 10) ; => #f; Quote syntax
'(1 2 3 4)
'(a b c d)
'() ; empty list
; List function
(list 1 2 3 4) ; => (1 2 3 4)
(list 'a 'b 'c) ; => (a b c)
; cons - builds a list by adding to front
(cons 1 '(2 3 4)) ; => (1 2 3 4)
(cons 'a '(b c)) ; => (a b c)
(cons 1 '()) ; => (1); car - get first element (head)
(car '(1 2 3)) ; => 1
(car '(a b c)) ; => a
; cdr - get rest of list (tail)
(cdr '(1 2 3)) ; => (2 3)
(cdr '(a b c)) ; => (b c)
; Combining car and cdr
(cadr '(1 2 3)) ; => 2 (car of cdr)
(caddr '(1 2 3)) ; => 3 (car of cdr of cdr)
; null? - check if empty
(null? '()) ; => #t
(null? '(1 2)) ; => #f
; length
(length '(1 2 3 4)) ; => 4
(length '()) ; => 0
; append - combine lists
(append '(1 2) '(3 4)) ; => (1 2 3 4)
(append '(a b) '(c d) '(e f)) ; => (a b c d e f)
; reverse
(reverse '(1 2 3 4)) ; => (4 3 2 1)
; list-ref - get nth element (0-indexed)
(list-ref '(a b c d) 0) ; => a
(list-ref '(a b c d) 2) ; => c; Sum of list
(define (sum lst)
(if (null? lst)
0
(+ (car lst) (sum (cdr lst)))))
(sum '(1 2 3 4 5)) ; => 15
; Length (recursive)
(define (my-length lst)
(if (null? lst)
0
(+ 1 (my-length (cdr lst)))))
; Find maximum
(define (my-max lst)
(if (null? (cdr lst))
(car lst)
(let ((rest-max (my-max (cdr lst))))
(if (> (car lst) rest-max)
(car lst)
rest-max))))
(my-max '(3 7 2 9 1)) ; => 9
; Member check
(define (my-member? item lst)
(cond
((null? lst) #f)
((equal? item (car lst)) #t)
(else (my-member? item (cdr lst)))))
(my-member? 3 '(1 2 3 4)) ; => #t
(my-member? 5 '(1 2 3 4)) ; => #f
; Remove duplicates
(define (remove-dups lst)
(cond
((null? lst) '())
((member (car lst) (cdr lst))
(remove-dups (cdr lst)))
(else
(cons (car lst) (remove-dups (cdr lst))))))Functions that take other functions as arguments or return functions
; Apply function to each element
(map square '(1 2 3 4)) ; => (1 4 9 16)
(map (lambda (x) (* x 2)) '(1 2 3)) ; => (2 4 6)
(map abs '(-1 2 -3 4)) ; => (1 2 3 4)
; Map with multiple lists
(map + '(1 2 3) '(4 5 6)) ; => (5 7 9)
(map * '(1 2 3) '(4 5 6)) ; => (4 10 18); Keep only elements that satisfy predicate
(filter even? '(1 2 3 4 5 6)) ; => (2 4 6)
(filter odd? '(1 2 3 4 5 6)) ; => (1 3 5)
(filter (lambda (x) (> x 5)) '(1 3 7 4 9 2)) ; => (7 9)
; Custom filter example
(define (positive-only lst)
(filter (lambda (x) (> x 0)) lst))
(positive-only '(-3 5 -1 8 -9 2)) ; => (5 8 2); foldr - fold from the right
(foldr + 0 '(1 2 3 4)) ; => 10
(foldr * 1 '(1 2 3 4)) ; => 24
(foldr cons '() '(1 2 3)) ; => (1 2 3)
; foldl - fold from the left (more efficient)
(foldl + 0 '(1 2 3 4)) ; => 10
(foldl cons '() '(1 2 3)) ; => (3 2 1)
; Using fold for complex operations
(define (my-sum lst)
(foldr + 0 lst))
(define (my-product lst)
(foldr * 1 lst))
(define (count-if pred lst)
(foldr (lambda (x acc)
(if (pred x)
(+ 1 acc)
acc))
0
lst))
(count-if even? '(1 2 3 4 5 6)) ; => 3; Apply function to list as separate arguments
(apply + '(1 2 3 4)) ; => 10
(apply max '(3 7 2 9 1)) ; => 9
(apply string-append '("hello" " " "world")) ; => "hello world"; Function that returns a function
(define (make-adder n)
(lambda (x) (+ x n)))
(define add5 (make-adder 5))
(add5 10) ; => 15
(define add100 (make-adder 100))
(add100 10) ; => 110
; Function that takes a function
(define (twice f x)
(f (f x)))
(twice square 3) ; => 81 (square of square)
(twice (lambda (x) (+ x 1)) 5) ; => 7
; Compose functions
(define (compose f g)
(lambda (x) (f (g x))))
(define add1-then-square (compose square (lambda (x) (+ x 1))))
(add1-then-square 4) ; => 25; Create local variables
(let ((x 5)
(y 10))
(+ x y)) ; => 15
; More complex example
(define (quadratic a b c x)
(let ((discriminant (- (* b b) (* 4 a c))))
(+ (* a x x) (* b x) c)))
; Let with computation
(let ((x (+ 2 3))
(y (* 4 5)))
(+ x y)) ; => 25
; Practical example
(define (distance x1 y1 x2 y2)
(let ((dx (- x2 x1))
(dy (- y2 y1)))
(sqrt (+ (* dx dx) (* dy dy))))); let* allows later bindings to use earlier ones
(let* ((x 5)
(y (* x 2))
(z (+ x y)))
z) ; => 15
; This would NOT work with regular let:
; (let ((x 5)
; (y (* x 2))) ; x not in scope yet!
; ...)
; Practical example
(define (compute-grade homework midterm final)
(let* ((hw-weight 0.3)
(mid-weight 0.3)
(final-weight 0.4)
(weighted-hw (* homework hw-weight))
(weighted-mid (* midterm mid-weight))
(weighted-final (* final final-weight))
(total (+ weighted-hw weighted-mid weighted-final)))
total)); letrec allows recursive definitions
(letrec ((fact (lambda (n)
(if (<= n 1)
1
(* n (fact (- n 1)))))))
(fact 5)) ; => 120
; Mutual recursion
(letrec ((even? (lambda (n)
(if (= n 0)
#t
(odd? (- n 1)))))
(odd? (lambda (n)
(if (= n 0)
#f
(even? (- n 1))))))
(even? 10)) ; => #t; Factorial
(define (factorial n)
(if (<= n 1)
1
(* n (factorial (- n 1)))))
; Fibonacci
(define (fib n)
(cond
((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
; Power
(define (power base exp)
(if (= exp 0)
1
(* base (power base (- exp 1)))))
; GCD (Euclid's algorithm)
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b)))); Tail recursive factorial (more efficient)
(define (factorial-tail n)
(define (fact-helper n acc)
(if (<= n 1)
acc
(fact-helper (- n 1) (* n acc))))
(fact-helper n 1))
; Tail recursive sum
(define (sum-tail lst)
(define (sum-helper lst acc)
(if (null? lst)
acc
(sum-helper (cdr lst) (+ acc (car lst)))))
(sum-helper lst 0))
; Tail recursive reverse
(define (reverse-tail lst)
(define (rev-helper lst acc)
(if (null? lst)
acc
(rev-helper (cdr lst) (cons (car lst) acc))))
(rev-helper lst '()))
(reverse-tail '(1 2 3 4)) ; => (4 3 2 1); Map implementation
(define (my-map f lst)
(if (null? lst)
'()
(cons (f (car lst))
(my-map f (cdr lst)))))
; Filter implementation
(define (my-filter pred lst)
(cond
((null? lst) '())
((pred (car lst))
(cons (car lst) (my-filter pred (cdr lst))))
(else (my-filter pred (cdr lst)))))
; Range (like Python's range)
(define (range start end)
(if (>= start end)
'()
(cons start (range (+ start 1) end))))
(range 1 6) ; => (1 2 3 4 5)
; Repeat element n times
(define (repeat x n)
(if (<= n 0)
'()
(cons x (repeat x (- n 1)))))
(repeat 'a 5) ; => (a a a a a); Flatten nested list
(define (flatten lst)
(cond
((null? lst) '())
((list? (car lst))
(append (flatten (car lst))
(flatten (cdr lst))))
(else
(cons (car lst) (flatten (cdr lst))))))
(flatten '(1 (2 3) ((4) 5))) ; => (1 2 3 4 5)
; Zip two lists together
(define (zip lst1 lst2)
(if (or (null? lst1) (null? lst2))
'()
(cons (list (car lst1) (car lst2))
(zip (cdr lst1) (cdr lst2)))))
(zip '(1 2 3) '(a b c)) ; => ((1 a) (2 b) (3 c))
; Take first n elements
(define (take n lst)
(if (or (<= n 0) (null? lst))
'()
(cons (car lst) (take (- n 1) (cdr lst)))))
(take 3 '(1 2 3 4 5)) ; => (1 2 3)
; Drop first n elements
(define (drop n lst)
(if (or (<= n 0) (null? lst))
lst
(drop (- n 1) (cdr lst))))
(drop 2 '(1 2 3 4 5)) ; => (3 4 5)(define (quicksort lst)
(if (null? lst)
'()
(let ((pivot (car lst))
(rest (cdr lst)))
(append
(quicksort (filter (lambda (x) (< x pivot)) rest))
(list pivot)
(quicksort (filter (lambda (x) (>= x pivot)) rest))))))
(quicksort '(3 7 2 9 1 5 8)) ; => (1 2 3 5 7 8 9); Binary tree: (value left right) or ()
; Count nodes
(define (count-nodes tree)
(if (null? tree)
0
(+ 1
(count-nodes (cadr tree))
(count-nodes (caddr tree)))))
; Tree height
(define (tree-height tree)
(if (null? tree)
0
(+ 1 (max (tree-height (cadr tree))
(tree-height (caddr tree))))))
; Sum all values in tree
(define (sum-tree tree)
(if (null? tree)
0
(+ (car tree)
(sum-tree (cadr tree))
(sum-tree (caddr tree)))))
; Example tree
(define my-tree '(5 (3 (1 () ()) (4 () ())) (8 (6 () ()) (9 () ()))))
(count-nodes my-tree) ; => 7
(tree-height my-tree) ; => 3
(sum-tree my-tree) ; => 36; String to list of characters
(string->list "hello") ; => (#\h #\e #\l #\l #\o)
; List of characters to string
(list->string '(#\h #\i)) ; => "hi"
; Reverse a string
(define (reverse-string s)
(list->string (reverse (string->list s))))
(reverse-string "hello") ; => "olleh"
; Count vowels
(define (vowel? c)
(member c '(#\a #\e #\i #\o #\u #\A #\E #\I #\O #\U)))
(define (count-vowels s)
(length (filter vowel? (string->list s))))
(count-vowels "hello world") ; => 3; Process each element and build new list
(define (process-list lst)
(if (null? lst)
'()
(cons (process-item (car lst))
(process-list (cdr lst)))))
; Filter based on condition
(define (filter-list lst)
(cond
((null? lst) '())
((condition? (car lst))
(cons (car lst) (filter-list (cdr lst))))
(else (filter-list (cdr lst)))))
; Accumulate with helper
(define (accumulate lst)
(define (helper lst acc)
(if (null? lst)
acc
(helper (cdr lst) (combine (car lst) acc))))
(helper lst initial-value)); Use display to print debug info
(define (debug-factorial n)
(display "Computing factorial of: ")
(display n)
(newline)
(if (<= n 1)
1
(* n (debug-factorial (- n 1)))))
; Trace recursion depth
(define (trace-depth depth n)
(display "Depth: ")
(display depth)
(display " n: ")
(display n)
(newline)
(if (<= n 0)
0
(+ n (trace-depth (+ depth 1) (- n 1)))))car ; first
cdr ; rest
cons ; prepend
null? ; empty?
length ; size
append ; concatenate
reverse ; reverse
list-ref ; get nth
member ; contains?map ; transform
filter ; select
foldr ; reduce right
foldl ; reduce left
apply ; call with list
lambda ; anonymous fn+ - * /
quotient ; int div
remainder ; modulo
expt ; power
sqrt ; square root
abs ; absolute
max min ; extremes= ; numeric eq
< > <= >=
eq? ; pointer eq
eqv? ; value eq
equal? ; structural eq
and or not