iT邦幫忙

2018 iT 邦幫忙鐵人賽
DAY 4
0
Software Development

每天 Racket 3 分鐘系列 第 8

(list 'day-07 "組織你的資料 — Racket 基礎資料結構:Pair、List 與 Vector")

1. Lisp 之所以是 Lisp

Lisp 的全名,稱為 List Processor,顧名思義,在 Lisp 裡頭,最常見的資料結構就是 List。其實在 s 表示式裡頭,整個語言都是用 List 結構組成:(element1 element2 element3)。因此,在 Lisp 以及 s 表示式家族語言裡頭,都具有著這種稱為語法與資料的 homoiconicity 的特性。(台灣沒有適切翻譯,對岸則稱「同像性」)因此,處理 List,也是開發 Racket 過程中,極為頻繁且重要的事情。

在 Racket 裡頭,List 怎麼建立呢?你或許會想到,Python 裡頭,List 就是一對 [] 所包起來的東西,同樣的,在 Racket 裡頭,List 就是一對 () 所包起來的東西。但因為要與語法區別,所以前面加上單引號,如下:

(define abc '("a" "b" "c"))

除此之外,你也可以直接用 list 函式,包住所有的元素:

(define abc (list "a" "b" "c"))

若我們要取這個 List 的第一個元素,可以使用 car

(car abc)  ;; "a"

而要取剩餘的元素,可以使用 cdr

(cdr abc) ;; ("b" "c")

既然是 List,我們可不可以把東西加進去呢?像 (list-add abc "d") 那樣?在 Lisp 家族裡頭的 List 基本上是不可變的(immutable),亦即語言層面並不鼓勵你對這個值進行任何的變換操作,如果要加上任何一個東西,建議是建立一個新的 List:

(append abc (list "d"))

append 的操作,是對多個 List 進行結合,因此後頭接的,也應該把它包進一個 List 的結構中才行。但如果你不小心打了:

(append abc "d")

會看到:

("a" "b" "c" . "d")

怎麼有個 . 呢?

2. 雙雙對對

要回答上面的問題,我們要回到那時代。我們已經說到,程式語言的前人們,使用 s 表示式創造了 Lisp 這樣的一個語言。然而 s 表示式,它不只對應到了語法樹,它其實是二元樹的一種表達方式:

ast

於是,他們在節點之間,給一個點 .,來表達兩個一對的資料組。因此我們在今日,能用 cons,來建構一個 Pair:

(cons 2 3)  ;; (2 . 3)

然而,要表達上述那棵樹,我們要有多少節點呢?

(a . (1 . 1))

當節點多時,資料結構的表示會變得很複雜,因此後來便簡化成兩條原則:

  1. . 的右側接鄰一個 (,則 . ( 可以省卻
  2. 若連續的 Pair 最後接著一個空 List ('()),則 .('() 都可以省卻 [1]

而 Pair 也同樣具有 carcdr 的操作,並且 cdr 取到的不是一個 Collection,而是單一個元素:

(define p (cons 2 3))
(car p) ;; 2
(cdr p) ;; 3

還記得上面第二個簡化規則嗎?它有什麼作用呢?我們在 Racket 可以用這個方式,來建立一個 List:

(define nums (cons 1 (cons 2 (cons 3 '()))))  ;; '(1 2 3)

這代表著,其實 Pair 是 List 的基礎結構,而每個 List 的最後,都存在著一個 '()。因此,在 Racket 裡頭,我們可以用這個方式來做一個簡單的 map 操作:

(define map
  (lambda (proc lst)
    (if (null? lst)
        '()
        (cons (proc (car lst)) (map proc (cdr lst))))))
        
;; 假設你還留著上回的 square

(map square nums)  ;; '(1 4 9)

3. Racket 之所以是 Racket

其實,我一開始在學時,carcdr 這三個字,看起來很簡單,但我覺得很難記。所幸,Racket 之所以是 Racket,在於它有相當大量的開發者與資源,因此這兩個字,也被轉變成比較好記的 firstrest。因此,上述的 map 也可以這樣寫:

(define map
  (lambda (proc lst)
    (if (null? lst)
        '()
        (cons (proc (first lst)) (map proc (rest lst))))))

程式碼就親切多了!此外,Racket 可以用 carcdr 的合併呼叫,例如:

(cadr nums)  ;; 意即:(car (cdr nums)),取第二個:2

當然,如果你想直接取第二個,用 list-ref 就好了啦:

(list-ref nums 1)  ;; index 從 0 開始

4. 別忘了 Vector

但,你若對資料結構有些概念,就會知道 List 的好處是可以動態擴充,而缺點也在於即使你呼叫 list-ref ,它也是線性尋訪,因此是一個一個 car 進去:

(define list-iter
  (lambda (lst idx)
    (if (= idx 0)
      (car lst)
      (list-iter (cdr lst) (- idx 1)))))

這時你或許會想問,Racket 有沒有像陣列一樣,靜態配置的一種資料結構呢?

答案是肯定的,它叫 Vector,在很早期的 Java 裡,也有個叫 Vector 的容器呢!

Vector 的字面表示就與 List 有所區隔,使用 #( 來表示:

(define v1 #(1 2 3))

當然,Vector 也有用函式呼叫來建置的方式:

(define v2 (vector 1 2 3))

只是,這點很重要: 在 Racket 裡頭,其實沒有像 C/Java/C# 家族那種 type array 的表示,例如 int[] 。而我們透過上述的方式所建立的 Vector 也如前所述,是一種 immutable 的資料結構,如果你要建立一個空的 Vector,可以塞值進去,可以這麼做:

(define v3 (make-vector 10 0))  ;; '#(0 0 0 0 0 0 0 0 0 0)

這樣會建立固定 10 個,每個皆為 0 的 mutable Vector,而 0 這參數可以省略。因此,要設定某個位置的值,可以使用:

(vector-set! v3 1 1)  ;; '#(0 1 0 0 0 0 0 0 0 0)
(vector-set! v3 2 3)  ;; '#(0 1 3 0 0 0 0 0 0 0)

上一篇
(display "λf.(λx.f (x x)) (λx.f (x x)) — day-06 — Racket 的 Function 與 Lambda — 1")
下一篇
(cond ((not (day-08?)) 'all-right) (else "我若不在寫 Racket,就在去寫 Racket 的路上 — Racket 的控制結構"))
系列文
每天 Racket 3 分鐘17

尚未有邦友留言

立即登入留言