2.3列表，迭代和递归

Racket是lisp的方言，它起初的意思是 “LISt Processor”。 内建的list数据结构保留了这种语言特征。
list函数接受多个值并且返回包含多个值的列表。list在repl里面打印有一个<code>'</code>和一对括号。

2.3.1预定义list循环

recket包含了很多函数迭代list。
map使用每一个元素的结果构造一个新的list
andmap,ormap使用and或者or来联合结果
filter 过滤非#f的元素
map,andmap,ormap.filter都可以接受多个list，所有list都相同长度，且函数必须针对每个列表有一个参数。
foldl 迭代每个元素，并合并迭代的结果到当前值。所以foldl函数需要一个初始化值。

2.3.2 list原始迭代

non-empty list操作
first:返回列表第一个元素
rest:返回剩下的列表
empty 常量，空列表
cons 增加元素到列表头
为了处理一个列表，需要处理空列表和非空列表。因为first和rest只能工作在非空列表上。empty?判断是否是空列表。cons?判断非空列表。
使用这些原始函数，你能构造length函数，map函数。

 (define (my-length lst)
    (cond 
    [(empty? lst) 0]
    [else (+ 1 (my-length (rest lst)))]))

(define (my-map f lst)
    (cond
      [(empty? lst)  empty]
      [else (cons (f (first lst)) 
                       (my-map f (rest lst)))]))

---

2.3.3 尾递归

my-length和my-map函数都是O(n)的。my-leng 函数需要堆叠（+ 1 ···）直到列表耗尽，然后才开始累加。

(my-length (list "a" "b" "c"))
= (+ 1 (my-length (list "b" "c")))
= (+ 1 (+ 1 (my-length (list "c"))))
= (+ 1 (+ 1 (+ 1 (my-length (list)))))
= (+ 1 (+ 1 (+ 1 0)))
= (+ 1 (+ 1 1))
= (+ 1 2)
= 3

我们更够改进计算方式避免额外的步骤。

(define (my-length lst)
; local function iter:
  (define (iter lst len)
  (cond
     [(empty? lst) len]
     [else (iter (rest lst) (+ len 1))]))
     ; body of my-length calls iter:
     (iter lst 0))

上面函数的调用<code>(iter (list "b" "c") 1) </code>实际上是<code>(iter (list "b") 2) </code>的值，第一个表达式的不需要等待第二个表达式返回。
上面这种求值得行为叫做尾递归优化。但是在reacket里面，它不只是一种优化。它是保证代码运行的手段。
对于my-map函数，也可以修改成尾递归。唯一要注意的是，累积的list是逆序的，你要反转它。可以使用for/list 来改进my-map，它只是一种的语法糖。

(define (my-app f lst)
  (for/list ([i lst])
    (f i)))

2.3.4递归vs迭代

my-length和my-map的例子证明迭代只是一种递归的特殊情况。在很多语言中，使用迭代的形式是很重要的，否则，性能会很差，当数据量很大的时候，还会堆栈溢出。Racket的情况也类似，有时候使用尾递归是很重要的，它可以避免O(n)的空间消耗，因为它值在一个常量空间里执行。
与此同时，递归在racket里面不会导致特别差的性能，也不会产生堆栈的溢出。你可能会导致内存溢出如果执行了太多的上下文，但是耗尽内存代表你调用了大量的深度递归，在其他语言中，这种情况会产生堆栈溢出。基于上面的描述，racket程序员应该拥抱递归而不是避免它们。
比如，从一个列表中移除连续的重复。

(define (remove-dups l)
    (cond
      [(empty? l) empty]
      [(empty? (rest l)) l]
      [else 
        (let ([i (first l)])
          (if (equal? i (first (rest l)))
          (remove-dups (rest l))
          (cons i (remove-dups (rest l)))))]))

总的来说，上面这个函数在输入长度n的列表时消耗O(n)的空间，但是这并没有什么问题，因为它产生O(n)的结果。如果列表恰好重复度比较高，那么结果会小于O(n)，而且
remove-dups的使用空间也小于O(n)。这是因为在丢弃重复时，函数直接返回remove-dups的结果，所以产生了尾递归优化。