Racket Lists and Recursion — Car, Cdr, Cons, and Structural Recursion
In this tutorial, you will learn about Racket Lists and Recursion. We cover key concepts, practical examples, and best practices to help you master this topic.
Lists are the heart of Racket. Everything — code, data, programs — is represented as lists. Understanding how lists work at the cons-cell level gives you deep insight into the language.
In this tutorial, you'll master Racket's list operations and recursion patterns.
What You'll Learn
- Cons cells (pairs)
- Car, cdr, and combinations
- Structural recursion on lists
- Common list operations
- Higher-order functions
- List comprehensions (for/list)
Cons Cells
; A cons cell has two parts: car and cdr
(cons 1 '()) ; => '(1)
(cons 1 (cons 2 '())) ; => '(1 2)
(cons 1 (cons 2 (cons 3 '()))) ; => '(1 2 3)
; Lists are chains of cons cells ending with empty
'(1 2 3) ; is syntactic sugar for (cons 1 (cons 2 (cons 3 '())))
Accessors
(define lst '(1 2 3 4 5))
; Basic accessors
(car lst) ; => 1 (first element)
(cdr lst) ; => '(2 3 4 5) (rest of list)
; Combinations (up to 4 levels)
(cadr lst) ; => 2 (car of cdr)
(caddr lst) ; => 3 (car of cdr of cdr)
(cddr lst) ; => '(3 4 5) (cdr of cdr)
; Modern aliases
(first lst) ; => 1
(rest lst) ; => '(2 3 4 5)
(second lst) ; => 2
Structural Recursion
; Every list is either:
; 1. empty (null)
; 2. (cons first rest)
; Length of a list
(define (my-length lst)
(if (empty? lst)
0
(+ 1 (my-length (rest lst)))))
(my-length '(a b c d)) ; => 4
; Sum of numbers
(define (sum lst)
(cond
[(empty? lst) 0]
[else (+ (first lst) (sum (rest lst)))]))
(sum '(1 2 3 4)) ; => 10
; Find element
(define (my-member x lst)
(cond
[(empty? lst) #f]
[(equal? x (first lst)) lst]
[else (my-member x (rest lst))]))
(my-member 3 '(1 2 3 4)) ; => '(3 4)
(my-member 9 '(1 2 3 4)) ; => #f
Higher-Order List Functions
; map: apply function to every element
(map sqr '(1 2 3 4)) ; => '(1 4 9 16)
(map string-upcase '("a" "b" "c")) ; => '("A" "B" "C")
; filter: keep elements satisfying predicate
(filter even? '(1 2 3 4 5 6)) ; => '(2 4 6)
(filter (lambda (x) (> x 10)) '(5 15 8 20)) ; => '(15 20)
; foldl: left fold (accumulate)
(foldl + 0 '(1 2 3 4)) ; => 10
(foldl (lambda (x acc) (cons x acc)) '() '(1 2 3)) ; => '(3 2 1)
; andmap, ormap
(andmap even? '(2 4 6)) ; => #t
(ormap odd? '(2 3 4)) ; => #t
for/list Comprehensions
; List comprehensions (more readable than map/filter)
(for/list ([i '(1 2 3 4)])
(* i i)) ; => '(1 4 9 16)
; With filtering
(for/list ([i '(1 2 3 4 5 6)]
#:when (even? i))
i) ; => '(2 4 6)
; Nested loops
(for/list ([i '(1 2)]
[j '(a b)])
(list i j)) ; => '((1 a) (1 b) (2 a) (2 b))
; With range
(for/list ([i (in-range 1 6)])
i) ; => '(1 2 3 4 5)
Practice Questions
Write a recursive function to count how many times a given element appears in a list.
Use map to convert a list of strings to uppercase.
Use filter to keep only strings longer than 3 characters from a list.
Write a recursive function that returns the last element of a list.
Use foldl to compute the product of a list of numbers.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro