;; 创建序对
(define p (cons 1 2))
p               ; => (1 . 2)

;; 访问序对的两部分
(car p)         ; => 1  （first）
(cdr p)         ; => 2  （rest）

;; 序对可以包含任意类型
(cons "name" "Guile")    ; => ("name" . "Guile")
(cons 'key 42)           ; => (key . 42)
(cons '(1 2) '(3 4))    ; => ((1 2) 3 4)

;; 修改序对（如果使用 set-car! / set-cdr!）
(define q (cons 1 2))
(set-car! q 10)
(set-cdr! q 20)
q               ; => (10 . 20)

(pair? '(1 . 2))     ; => #t
(pair? '(1 2 3))     ; => #t（列表也是序对）
(pair? '())          ; => #f（空列表不是序对）
(pair? 42)           ; => #f
(pair? "hello")      ; => #f

;; 创建列表的多种方式

;; 1. 列表字面量
'(1 2 3 4 5)

;; 2. list 函数
(list 1 2 3 4 5)

;; 3. 用 cons 构造
(cons 1 (cons 2 (cons 3 '())))

;; 4. 用 append 拼接
(append '(1 2) '(3 4) '(5))

;; 5. 用 iota 生成数字序列
(iota 5)              ; => (0 1 2 3 4)
(iota 5 1)            ; => (1 2 3 4 5)
(iota 5 0 2)          ; => (0 2 4 6 8)

;; 6. 空列表
'()
(list)

(define xs '(1 2 3 4 5))

;; 访问元素
(car xs)              ; => 1（第一个元素）
(cdr xs)              ; => (2 3 4 5)（其余元素）
(cadr xs)             ; => 2（第二个 = car of cdr）
(caddr xs)            ; => 3（第三个）
(cadddr xs)           ; => 4（第四个）

;; 最多支持 4 层嵌套的 c[ad]+r 组合
;; cadr = (car (cdr xs))
;; caar = (car (car xs))  —— 用于嵌套列表
;; cdar = (cdr (car xs))

;; SRFI-1 提供了更方便的访问方式
(use-modules (srfi srfi-1))

(first xs)            ; => 1
(second xs)           ; => 2
(third xs)            ; => 3
(fourth xs)           ; => 4
(fifth xs)            ; => 5
(last xs)             ; => 5
(length xs)           ; => 5

;; 列表谓词
(null? '())           ; => #t（空列表？）
(list? '(1 2 3))      ; => #t
(pair? '(1 2 3))      ; => #t（非空列表也是序对）
(proper-list? '(1 2 3))  ; => #t
(circular-list? '(1 2 3))  ; => #f

;; cons —— 在头部添加
(cons 0 '(1 2 3))     ; => (0 1 2 3)

;; append —— 拼接列表
(append '(1 2) '(3 4))  ; => (1 2 3 4)
(append '(1) '(2) '(3)) ; => (1 2 3)

;; 注意：append 的最后一个参数可以不是列表
(append '(1 2) 3)     ; => (1 2 . 3)（点对！）

;; list —— 创建新列表
(list 1 2 3)          ; => (1 2 3)

;; make-list —— 创建重复列表
(make-list 5 0)       ; => (0 0 0 0 0)

;; reverse —— 反转
(reverse '(1 2 3 4))  ; => (4 3 2 1)

;; 取子列表
(take '(1 2 3 4 5) 3)   ; => (1 2 3)
(drop '(1 2 3 4 5) 3)   ; => (4 5)
(take-right '(1 2 3 4 5) 2)  ; => (4 5)
(drop-right '(1 2 3 4 5) 2)  ; => (1 2 3)

;; 分割列表
(split-at '(1 2 3 4 5) 3)  ; => (1 2 3) and (4 5)（两个值）

(use-modules (srfi srfi-1))

;; 高级列表操作（SRFI-1）

;; filter —— 过滤
(filter even? '(1 2 3 4 5 6))     ; => (2 4 6)
(filter odd? '(1 2 3 4 5 6))      ; => (1 3 5)

;; remove —— 移除满足条件的
(remove even? '(1 2 3 4 5 6))     ; => (1 3 5)

;; partition —— 分区
(partition even? '(1 2 3 4 5 6))
;; => (2 4 6) and (1 3 5)

;; find —— 查找第一个
(find even? '(1 3 4 7 8))         ; => 4

;; any / every —— 存在/所有
(any even? '(1 3 4 7))            ; => #t
(every even? '(2 4 6))            ; => #t
(every even? '(2 3 4))            ; => #f

;; count —— 计数
(count even? '(1 2 3 4 5))        ; => 2

;; 删除重复
(delete-duplicates '(1 2 1 3 2 4))  ; => (1 2 3 4)

;; 排序
(sort '(3 1 4 1 5 9) <)           ; => (1 1 3 4 5 9)
(sort '(3 1 4 1 5 9) >)           ; => (9 5 4 3 1 1)

;; 字符串列表排序
(sort '("banana" "apple" "cherry") string<?)
;; => ("apple" "banana" "cherry")

;; 关联列表排序
(sort '((3 . "c") (1 . "a") (2 . "b"))
      (lambda (a b) (< (car a) (car b))))
;; => ((1 . "a") (2 . "b") (3 . "c"))

(use-modules (srfi srfi-1))

;; 集合操作（将列表视为集合）

;; 并集
(lset-union = '(1 2 3) '(2 3 4))       ; => (1 2 3 4)

;; 交集
(lset-intersection = '(1 2 3) '(2 3 4)) ; => (2 3)

;; 差集
(lset-difference = '(1 2 3 4) '(2 4))   ; => (1 3)

;; 子集判断
(lset<= = '(1 2) '(1 2 3))             ; => #t

;; 成员判断
(member 3 '(1 2 3 4))                   ; => (3 4)
(memq 'b '(a b c))                      ; => (b c)
(memv 3 '(1 2 3 4))                     ; => (3 4)

;; 创建关联列表
(define al '((name . "Guile")
             (version . 3)
             (license . "GPL")))

;; 查找（assq 使用 eq? 比较）
(assq al 'name)       ; => (name . "Guile")
(assq-ref al 'name)   ; => "Guile"（更简洁）
(assq-ref al 'version) ; => 3

;; 查找（assoc 使用 equal? 比较，适用于字符串键）
(define al2 '(("name" . "Guile")
              ("version" . 3)))
(assoc-ref al2 "name")  ; => "Guile"

;; 添加（cons 到头部，返回新列表）
(define al3 (acons 'author "GNU" al))
(assq-ref al3 'author)  ; => "GNU"

;; 修改（返回新列表）
(define (alist-set alist key value)
  "在关联列表中设置键值，覆盖已有值"
  (acons key value
         (alist-delete key alist eq?)))

(define al4 (alist-set al 'version 4))
(assq-ref al4 'version)  ; => 4

;; 遍历
(for-each
  (lambda (pair)
    (format #t "~a: ~a~%" (car pair) (cdr pair)))
  al)

;; 1. 求列表长度（递归版）
(define (my-length lst)
  (if (null? lst)
      0
      (+ 1 (my-length (cdr lst)))))

(my-length '(1 2 3 4 5))  ; => 5

;; 2. 求和
(define (sum lst)
  (if (null? lst)
      0
      (+ (car lst) (sum (cdr lst)))))

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

;; 3. 查找元素
(define (my-member item lst)
  (cond
    ((null? lst) #f)
    ((equal? item (car lst)) lst)
    (else (my-member item (cdr lst)))))

(my-member 3 '(1 2 3 4 5))  ; => (3 4 5)

;; 4. 列表反转（尾递归优化）
(define (reverse! lst)
  (let loop ((lst lst) (acc '()))
    (if (null? lst)
        acc
        (loop (cdr lst) (cons (car lst) acc)))))

(reverse! '(1 2 3 4 5))  ; => (5 4 3 2 1)

;; 5. 映射（自实现 map）
(define (my-map f lst)
  (if (null? lst)
      '()
      (cons (f (car lst))
            (my-map f (cdr lst)))))

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

;; 非尾递归版本 —— 会消耗 O(n) 栈空间
(define (factorial-bad n)
  (if (<= n 1)
      1
      (* n (factorial-bad (- n 1)))))

;; 尾递归版本 —— Guile 优化为 O(1) 空间
(define (factorial-good n)
  (let loop ((n n) (acc 1))
    (if (<= n 1)
        acc
        (loop (- n 1) (* n acc)))))

;; 尾递归的关键：递归调用是表达式的最后一个操作
;; (loop ...) 在 (* n acc) 计算后直接返回，不保留调用帧

;; 尾递归版本的列表处理
(define (map-tail f lst)
  (let loop ((lst lst) (acc '()))
    (if (null? lst)
        (reverse acc)  ; 注意：需要反转
        (loop (cdr lst) (cons (f (car lst)) acc)))))

(map-tail (lambda (x) (* x 2)) '(1 2 3 4 5))
; => (2 4 6 8 10)

;; 列表可以嵌套，形成树结构
;; 树递归：同时递归 car 和 cdr

;; 扁平化（将嵌套列表转为一维列表）
(define (flatten tree)
  (cond
    ((null? tree) '())
    ((pair? tree)
     (append (flatten (car tree))
             (flatten (cdr tree))))
    (else (list tree))))

(flatten '(1 (2 (3 4) 5) (6 7)))
; => (1 2 3 4 5 6 7)

;; 树中的查找
(define (tree-find pred tree)
  (cond
    ((null? tree) #f)
    ((pair? tree)
     (or (tree-find pred (car tree))
         (tree-find pred (cdr tree))))
    (else (and (pred tree) tree))))

(tree-find (lambda (x) (= x 4)) '(1 (2 3) (4 5)))
; => 4

;; 正当列表（proper list）—— 以空列表结尾
'(1 2 3)              ; 等价于 (1 . (2 . (3 . ())))

;; 不正当列表（improper list / dotted list）—— 以非空结尾
(cons 1 (cons 2 3))   ; => (1 2 . 3)

;; 环形列表（circular list）
(define circ (list 1 2 3))
(set-cdr! (last-pair circ) circ)
;; circ 现在是 (1 2 3 1 2 3 1 2 3 ...)

;; 检测列表类型
(proper-list? '(1 2 3))    ; => #t
(pair? '(1 2 . 3))         ; => #t
(null? '())                ; => #t

;; 使用关联列表处理 CSV 数据
(define csv-data
  '(("name" "age" "city")
    ("Alice" "30" "Beijing")
    ("Bob" "25" "Shanghai")
    ("Charlie" "35" "Shenzhen")))

;; 将 CSV 转换为记录列表
(define (csv->records csv)
  (let ((headers (car csv))
        (rows (cdr csv)))
    (map (lambda (row)
           (map cons headers row))
         rows)))

(define records (csv->records csv-data))
;; 结果：
;; (((name . "Alice") (age . "30") (city . "Beijing"))
;;  ((name . "Bob") (age . "25") (city . "Shanghai"))
;;  ((name . "Charlie") (age . "35") (city . "Shenzhen")))

;; 查询记录
(define (record-get record field)
  (assq-ref record field))

(record-get (car records) 'name)  ; => "Alice"

;; 过滤记录
(filter (lambda (record)
          (> (string->number (assq-ref record 'age)) 28))
        records)
;; => (((name . "Alice") ...) ((name . "Charlie") ...))

;; 使用列表实现栈（LIFO）
(define (make-stack) (list 'stack))

(define (stack-push stack item)
  (cons 'stack (cons item (cdr stack))))

(define (stack-pop stack)
  (if (null? (cdr stack))
      (error "Stack underflow")
      (values (cadr stack)
              (cons 'stack (cddr stack)))))

(define (stack-peek stack)
  (if (null? (cdr stack))
      (error "Stack is empty")
      (cadr stack)))

(define (stack-empty? stack)
  (null? (cdr stack)))

;; 使用示例
(define s (make-stack))
(set! s (stack-push s 1))
(set! s (stack-push s 2))
(set! s (stack-push s 3))
(stack-peek s)  ; => 3