Racket是lisp的方言，它起初的意思是 “LISt Processor”。 內(nèi)建的list數(shù)據(jù)結(jié)構(gòu)保留了這種語言特征。
list函數(shù)接受多個值并且返回包含多個值的列表。list在repl里面打印有一個<code>'</code>和一對括號。

2.3.1預(yù)定義list循環(huán)

recket包含了很多函數(shù)迭代list。
map使用每一個元素的結(jié)果構(gòu)造一個新的list
andmap,ormap使用and或者or來聯(lián)合結(jié)果
filter 過濾非#f的元素
map,andmap,ormap.filter都可以接受多個list，所有l(wèi)ist都相同長度，且函數(shù)必須針對每個列表有一個參數(shù)。
foldl 迭代每個元素，并合并迭代的結(jié)果到當(dāng)前值。所以foldl函數(shù)需要一個初始化值。

2.3.2 list原始迭代

non-empty list操作
first:返回列表第一個元素
rest:返回剩下的列表
empty 常量，空列表
cons 增加元素到列表頭
為了處理一個列表，需要處理空列表和非空列表。因?yàn)閒irst和rest只能工作在非空列表上。empty?判斷是否是空列表。cons?判斷非空列表。
使用這些原始函數(shù)，你能構(gòu)造length函數(shù)，map函數(shù)。

 (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函數(shù)都是O(n)的。my-leng 函數(shù)需要堆疊（+ 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

我們更夠改進(jìn)計(jì)算方式避免額外的步驟。

(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))

上面函數(shù)的調(diào)用<code>(iter (list "b" "c") 1) </code>實(shí)際上是<code>(iter (list "b") 2) </code>的值，第一個表達(dá)式的不需要等待第二個表達(dá)式返回。
上面這種求值得行為叫做尾遞歸優(yōu)化。但是在reacket里面，它不只是一種優(yōu)化。它是保證代碼運(yùn)行的手段。
對于my-map函數(shù)，也可以修改成尾遞歸。唯一要注意的是，累積的list是逆序的，你要反轉(zhuǎn)它?？梢允褂胒or/list 來改進(jìn)my-map，它只是一種的語法糖。

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

2.3.4遞歸vs迭代

my-length和my-map的例子證明迭代只是一種遞歸的特殊情況。在很多語言中，使用迭代的形式是很重要的，否則，性能會很差，當(dāng)數(shù)據(jù)量很大的時候，還會堆棧溢出。Racket的情況也類似，有時候使用尾遞歸是很重要的，它可以避免O(n)的空間消耗，因?yàn)樗翟谝粋€常量空間里執(zhí)行。
與此同時，遞歸在racket里面不會導(dǎo)致特別差的性能，也不會產(chǎn)生堆棧的溢出。你可能會導(dǎo)致內(nèi)存溢出如果執(zhí)行了太多的上下文，但是耗盡內(nèi)存代表你調(diào)用了大量的深度遞歸，在其他語言中，這種情況會產(chǎn)生堆棧溢出。基于上面的描述，racket程序員應(yīng)該擁抱遞歸而不是避免它們。
比如，從一個列表中移除連續(xù)的重復(fù)。

(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)))))]))

總的來說，上面這個函數(shù)在輸入長度n的列表時消耗O(n)的空間，但是這并沒有什么問題，因?yàn)樗a(chǎn)生O(n)的結(jié)果。如果列表恰好重復(fù)度比較高，那么結(jié)果會小于O(n)，而且
remove-dups的使用空間也小于O(n)。這是因?yàn)樵趤G棄重復(fù)時，函數(shù)直接返回remove-dups的結(jié)果，所以產(chǎn)生了尾遞歸優(yōu)化。