列表与递归

深入列表操作与递归思维，包括尾递归优化和常用列表高阶函数。

列表：Racket 的灵魂

#lang racket

;; 构造列表
'(1 2 3)                         ; 引用构造
(list 1 2 3)                     ; 函数构造
(cons 0 '(1 2 3))                ; => '(0 1 2 3)

;; 拆解列表
(car '(1 2 3))                   ; => 1
(cdr '(1 2 3))                   ; => '(2 3)

递归思维

递归是处理列表的核心方式：

;; 求列表长度
(define (my-length lst)
  (if (null? lst)
      0
      (+ 1 (my-length (cdr lst)))))

;; 反转列表
(define (my-reverse lst)
  (if (null? lst)
      '()
      (append (my-reverse (cdr lst))
              (list (car lst)))))

尾递归优化

尾递归不会导致栈溢出，因为它可以被编译器优化为循环：

;; 非尾递归（可能溢出）
(define (sum lst)
  (if (null? lst)
      0
      (+ (car lst) (sum (cdr lst)))))

;; 尾递归（安全）
(define (sum-tail lst)
  (let loop ([rest lst] [acc 0])
    (if (null? rest)
        acc
        (loop (cdr rest) (+ acc (car rest))))))

(sum-tail '(1 2 3 4 5))  ; => 15

列表高阶函数

;; map
(map (lambda (x) (* x x)) '(1 2 3 4 5))
; => '(1 4 9 16 25)

;; filter
(filter even? '(1 2 3 4 5 6))
; => '(2 4 6)

;; foldl / foldr
(foldl + 0 '(1 2 3 4 5))  ; => 15
(foldl cons '() '(1 2 3)) ; => '(3 2 1)
(foldr cons '() '(1 2 3)) ; => '(1 2 3)

;; andmap / ormap
(andmap positive? '(1 2 3))   ; => #t
(ormap even? '(1 3 5 7 8))    ; => #t

常用列表操作

(append '(1 2) '(3 4))     ; => '(1 2 3 4)
(reverse '(1 2 3))          ; => '(3 2 1)
(sort '(3 1 4 1 5) <)      ; => '(1 1 3 4 5)
(take '(1 2 3 4 5) 3)       ; => '(1 2 3)
(drop '(1 2 3 4 5) 3)       ; => '(4 5)
(assoc 'b '((a 1) (b 2)))   ; => '(b 2)

小结

列表和递归是 Racket 编程的基石。掌握 car/cdr/cons 三件套、尾递归优化和 map/filter/fold 高阶函数，是成为高效 Racket 程序员的关键。