第二章：數據結構 · Scheme 語言簡明教程

第二章數據類型 =============== 數據類型是一組相關的值信息集。各種數據類型互相聯系，而且它們通常是具有層次關系。Scheme擁有豐富的數據類型：有一些是簡單的類型，還有一些復合類型由其它的類型組合而成。 ## 2.1 簡單數據類型 Scheme中的簡單數據類型包含 `booleans` (布爾類型) , `number`(數字類型), `characters`(字符類型) 和 `symbols`(標識符類型)。 ### 2.1.1 Booleans Scheme中的booleans類型用 `#t`、`#f`來分別表示true和false。Scheme擁有一個叫`boolean?`的過程，可以用來檢測它的參數是否為boolean類型。 ``` (boolean? #t) => #t (boolean? "Hello, World!") => #f ``` 而`not`過程則直接取其參數的相反值做為boolean類型結果。 ``` (not #f) => #t (not #t) => #f (not "Hello, World!") => #f ``` 最后一個表達式清晰的顯示出了Scheme的一個便捷性：在一個需要boolean類型的上下文中，Scheme會將任何非 `#f`的值看成true。 ### 2.1.2 Numbers Scheme的numbers類型可以是`integers`(整型，例如`42`)，`rationals`(有理數，例如`22/7`)，`reals`(實數，例如`3.14159`)，或`complex`(復數，`2+3i`)。一個整數是一個有理數，一個有理數是一個實數，一個實數是一個復數，一個復數是一個數字。 Scheme中有可供各種數字進行類型判斷的過程： ```scheme (number? 42) => #t (number? #t) => #f (complex? 2+3i) => #t (real? 2+3i) => #f (real? 3.1416) => #t (real? 22/7) => #t (real? 42) => #t (rational? 2+3i) => #f (rational? 3.1416) => #t (rational? 22/7) => #t (integer? 22/7) => #f (integer? 42) => #t ``` Scheme的integers(整型)不需要一定是10進制格式。可以通過在數字前加前綴 `#b` 來規定實現2進制。這樣 `#b1100`就是10進制數字12了。實現8進制和16進制格式的前綴分別是 `#o` 和` #x`。(decimal前綴 `#d`是可選項) 我們可以使用通用相等判斷過程 `eqv?` 來檢測數字的相等性。(`eqv?`有點類似引用的相等判斷ReferenceEquals) ```scheme (eqv? 42 42) => #t (eqv? 42 #f) => #f (eqv? 42 42.0) => #f ``` 不過，如果你知道參與比較的參數全是數字，選擇專門用來進行數字相等判斷的` = `會更合適些。(`= `號運算時會根據需要對參數做類型轉換，如` (= 42 "42")` 運算結果是 `#t`) ```scheme (= 42 42) => #t (= 42 #f) -->ERROR!!! (= 42 42.0) => #t ``` 其它的數字比較還包括 `<`,` <=`,` >`,` >=` ```scheme (< 3 2) => #f (>= 4.5 3) => #t ``` `+`, `-`,` *`,` /`, `expt`等數學運算過程具有我們期待的功能。 ```scheme (+ 1 2 3) => 6 (- 5.3 2) => 3.3 (- 5 2 1) => 2 (* 1 2 3) => 6 (/ 6 3) => 2 (/ 22 7) => 22/7 (expt 2 3) => 8 (expt 4 1/2) => 2.0 ``` 對于一個參數的情況，`-` 和` / `過程會分別得到反數和倒數的結果。 `max`和`min` 過程會分別返回提供給它們的參數的最大值和最小值。它們可以支持任何的數字。 ```scheme (max 1 3 4 2 3) => 4 (min 1 3 4 2 3) => 1 ``` `abs`過程會返回提供給它參數的絕對值。 ```scheme (abs 3) => 3 (abs -4) => 4 ``` 這些還只是冰山一角。Scheme提供一整套豐富數學和三角運算過程。比如` atan`, `exp`, 和 `sqrt`等過程分別返回參數的余切、自然反對數和開方值。其它更具體的數學運算過程信息請參閱Revised^5 Report on the Algorithmic Language Scheme ---- ### 2.1.3 Characters Scheme中字符型數據通過在字符前加 `#\`前綴來表示。像` #\c`就表示字符` c`。那些非可視字符會有更多的描述名稱，例如，`#\newline`, `#\tab`。空格字符可以寫成 `#\ `，或者可讀性更好一些的`#\space`。字符類型判斷過程是`char?` ： ```scheme (char? #\c) => #t (char? 1) => #f (char? #\;) => #t ``` 需要注意的是數據的分號字符不會引發注釋。字符類型數據有自己的比較判斷過程：`char=?`, `char<?`, `char<=?`, `char>?`, `char>=?` ```scheme (char=? #\a #\a) => #t (char<? #\a #\b) => #t (char>=? #\a #\b) => #f ``` 要實現忽略大小寫的比較，得使用` char-ci` 過程代替` char`過程： ```scheme (char-ci=? #\a #\A) => #t (char-ci<? #\a #\B) => #t ``` 而類型轉換過程分別是 `char-downcase` 和`char-upcase`： ```scheme (char-downcase #\A) => #\a (char-upcase #\a) => #\A ``` ---- ### 2.1.4 Symbols 前面我們所見到的簡單數據類型都是自運算的。也就是如果你在命令提示符后輸入了任何這些類型的數據，運算后會返回和你輸入內容是一樣的結果。 ```scheme #t => #t 42 => 42 #\c => #\c ``` Symbols并沒有相同的表現方式。這是因為symbols通常在Scheme程序中被用來當做變量的標識，這樣可以運算出變量所承載的值。然而symbols是一種簡單數據類型，而且就像characers、numbers以及其它類型數據一樣，是Scheme中可以傳遞的有效值類型。創建一個單純的symbol而非變量時，你需要使用`quote`過程： ```scheme (quote xyz) => xyz ``` 因為在Scheme中經常要引用這種類型，我們有一種更簡便的方式。表達式 `'E`和` (quote E) `在Scheme中是等價的。 Scheme中symbols由一個字符串來命令。在命名時不要和其它類型數據發生沖突，比如characters 、booleans、numbers 或復合類型。像` this-is-a-symbol`，`i18n`，` <=>`，和`$!#*`都是symbols，而 `16`，`1+2i`，`#t`，`"this-is-a-string"`和`'("hello" "world")` 都不是symbols類型數據,`'("hello" "world")` 是一個只包含兩個字符串的List。用來檢查symbols類型數據的過程是`symbol?` ```scheme (symbol? 'xyz) => #t (symbol? 42) => #f ``` Scheme的symbols類型通常都是不區分大小寫的。因此`Calorie` 和`calorie`是等價的 ```scheme (eqv? 'Calorie 'calorie) => #t ``` 我們還可以使用` define` 將symbol 類型的數據如`xyz`當成一個全局的變量來使用： ```scheme (define xyz 9) ``` 這樣可以就創建了一個值為9的變量`xyz`.。如果現在直接在Scheme命令提示符后輸入`xyz`，這樣會將xyz中的值做為運算結果。 ```scheme xyz => 9 ``` 如果想改變`xyz`中的值可以用`set!`來實現： ```scheme (set! xyz #\c) ``` 現在`xyz`中的值就是字符` #\c`了。 ```scheme xyz => #\c ``` ## 2.2 復合數據類型復合數據類型是以組合的方式通過組合其它數據類型數據來獲得。 ---- ### 2.2.1，Strings 字符串類型是由字符組成的序列（不能和symbols混淆，symbols僅是由一組字符來命名的簡單類型）。你可以通過將一些字符包上閉合的雙引號來得到字符串。Strings是自運算類型。 ```scheme "Hello, World!" => "Hello, World!" ``` 還可以通過向`string` 過程傳遞一組字符并返回由它們合并成的字符串： ```scheme (string #\h #\e #\l #\l #\o) => "hello" ``` 現在讓我們定義一個全局字符串變量 `greeting`。 ```scheme (define greeting "Hello; Hello!") ``` 注意一個字符串數據中的分號不會得到注釋。一個給定字符串數據中的字符可以分別被訪問和更改。通過向`string-ref`過程傳遞一個字符串和一個從0開始的索引號，可以返回該字符串指定索引號位置的字符。 ```scheme (string-ref greeting 0) => #\H ``` 可以通在一個現有的字符串上追加其它字符串的方式來獲得新字符串： ```scheme (string-append "E " "Pluribus " "Unum") => "E Pluribus Unum" ``` 你可以定義一個指定長度的字符串，然后用期望的字符來填充它。 ```scheme (define a-3-char-long-string (make-string 3)) ``` 檢測一個值是否是字符串類型的過程是`string?`。通過調用`string`， `make-string` 和` string-append`獲得的字符串結果都是可修改的。而過程`string-set!`就可以替換字符串指定索引處的字符。 ```scheme (define hello (string #\H #\e #\l #\l #\o)) hello => "Hello" (string-set! hello 1 #\a) hello => "Hallo" ``` ### 2.2.2 Vectors (向量) Vectors是像strings一樣的序列，但它們的元素可以是任何類型，而不僅僅是字符，當然元素也可以是Vetors類型，這是一種生成多維向量的好方式。這使用五個整數創建了一個vector： ```scheme (vector 0 1 2 3 4) => #(0 1 2 3 4) ``` 注意Scheme表現一個向量值的方式：在用一對小括號包括起來的向量元素前面加了一個 `#` 字符。和`make-string`過程類似，過程`make-vectors`可以構建一個指定長度的向量： ```scheme (define v (make-vector 5)) ``` 而過程`vector-ref` 和` vector-set!`分別可以訪問和修改向量元素。檢測值是否是一個向量的過程是`vector?`。 ---- ### 2.2.3 Dotted pairs(點對) 和 lists(列表) 點對是將兩個任意數值組合成有序數偶的復合類型。點對的第一個數值被稱作car，第二值被稱作cdr，而將兩個值組合成點值對的過程是cons。 ```scheme (cons 1 #t) => (1 . #t) ``` 點對不能自運算，因此直接以值的方式來定義它們（即不通過調用`cons`來創建），必須顯式的使用引號： ```scheme '(1 . #t) => (1 . #t) (1 . #t) -->ERROR!!! ``` 訪問點值對值的過程分別是`car` (`car`訪問點值對的第一個元素)和 `cdr`(`cdr`訪問點值對的非一個元素)： ```scheme (define x (cons 1 #t)) (car x) => 1 (cdr x) => #t ``` 點對的元素可以通過修改器過程`set-car!` 和` set-cdr!`來進行修改： ```scheme (set-car! x 2) (set-cdr! x #f) x => (2 . #f) ``` 點對也可以包含其它的點對。 ```scheme (define y (cons (cons 1 2) 3)) y => ((1 . 2) . 3) ``` 這個點對的`car`運算結果`car`運算結果是`1`,而`car`運算結果的`cdr`運算結果是`2`。即: ```scheme (car (car y)) => 1 (cdr (car y)) => 2 ``` Scheme提供了可以簡化`car` 和` cdr`組合起來連續訪問操作的簡化過程。像`caar`表示”`car` 運算結果的 `car`運算結果”， `cdar`表示”`car`運算結果的`cdr`運算結果”，等等。 ```scheme (caar y) => 1 (cdar y) => 2 ``` 像c...r這樣風格的簡寫最多只支持四級連續操作。像`cadr`，`cdadr`，和 `cdaddr`都是存在的。而`cdadadr`這樣的就不對了。當第二個元素是一個嵌套的點對時，Scheme使用一種特殊的標記來表示表達式的結果： ```scheme (cons 1 (cons 2 (cons 3 (cons 4 5)))) => (1 2 3 4 . 5) ``` 即，`(1 2 3 4 . 5)`是對`(1 . (2 . (3 . (4 . 5))))`的一種簡化。這個表達式的最后一個`cdr`運算結果是5。如果嵌套點值對最后一個`cdr` 運算結果是一個空列表對象，Scheme提供了一種更進一步的用表達式`'()`來表示的簡化方式。空列表沒有被考慮做為可以自運算的值，所以為程序提供一個空列表值時必須用單引號方式來創建： ```scheme '() => () ``` 諸如像`(1 . (2 . (3 . (4 . ()))))`這樣形式的點值對被簡化成`(1 2 3 4)`。像這樣第二元素都是一個點值對特殊形式的嵌套點值對就稱作列表list。這是一個四個元素長度的列表。可以像這樣來創建： ```scheme (cons 1 (cons 2 (cons 3 (cons 4 '())))) ``` 但Scheme提供了一個list過程可以更方便的創建列表。List可以將任意個數的參數變成列表返回： ```scheme (list 1 2 3 4) => (1 2 3 4) ``` 實際上，如果我們知道列表所包含的所有元素，我們還可以用`quote` 來定義一個列表： ```scheme '(1 2 3 4) => (1 2 3 4) ``` 列表的元素可以通過指定索引號來訪問。 ```scheme (define y (list 1 2 3 4)) (list-ref y 0) => 1 (list-ref y 3) => 4 (list-tail y 1) => (2 3 4) (list-tail y 3) => (4) ``` `list-tail`返回了給定索引號后的所有元素。 `pair?`， `list?` 和` null?`判斷過程可以分別用來檢查它們的參數是不是一個點對，列表或空列表。 ```scheme (pair? '(1 . 2)) => #t (pair? '(1 2)) => #t (pair? '()) => #f (list? '()) => #t (null? '()) => #t (list? '(1 2)) => #t (list? '(1 . 2)) => #f (null? '(1 2)) => #f (null? '(1 . 2)) => #f ``` ### 2.2.1 數據類型轉換 Scheme提供了許多可以進行數據類型轉換的過程。我們已經知道可以通過`char-downcase` 和 `char-upcase`過程來進字符大小寫的轉換。字符還可以通過使用`char->integer`來轉換成整型，同樣的整型也可以通過`integer->char`被轉換成字符。(字符轉換成整型得到的結果通常是這個字符的ascii碼值。) ```scheme (char->integer #\d) => 100 (integer->char 50) => #\2 ``` 字符串可以被轉換成等價的字符列表。 ```scheme (string->list "hello") => (#\h #\e #\l #\l #\o) ``` 其它的轉換過程也都是一樣的風格`list->string`， `vector->list` 和 `list->vector`。數字可以轉換成字符串：`(number->string 16) => "16"` 字符串也可以轉換成數字。如果字符串不能轉換成數字，則會返回`#f`。 ```scheme (string->number "16") => 16 (string->number "Am I a not number?") => #f ``` `string->number`第二個參數是可選參數，指示以幾進制來轉換。 ```scheme (string->number "16" 8) => 14 ``` 八進制的數字 `16` 等于` 14`。 Symbols也可以轉換為字符串，反之亦然： ```scheme (symbol->string 'symbol) => "symbol" (string->symbol "string") => string ``` ## 2.3 其它數據類型 Scheme還包含了一些其它數據類型。一個是 *procedure* (過程)。我們已經見過了許多過程了，例如，`display`， `+`， `cons`等。實際上，它們是一些承載了過程值的變量，過程本身內部的數值和字符并不可見： ```scheme cons => <procedure> ``` 迄今為止我們所見過的這些過程都屬于原始過程（系統過程），由一些全局變量來承載它們。用戶還可以添加自定義的過程。還有另外種數據類型是port端口。一個端口是為輸入輸出提供執行的通道。端口通常會和文件和控制臺操作相關聯。在我們的`"Hello，World！"`程序中，我們使用`display`過程向控制臺輸出了一個字符串。`display`可以接受兩個參數，第一個參數值是將輸出的值，另一個值則表示了即將承載顯示結果的輸出port(端口)。在我們的程序中，`display`的第二參數是隱式參數。這時候`display`會采用標準輸出端口作為它的默認輸出端口。我們可以通過調用`current-output-port`過程來取得當前的標準輸出端口。我們可以更清楚的寫出: ```scheme (display "Hello, World!" (current-output-port)) ``` ## 2.4 S-expressions（S表達式）所有這些已經被討論過的數據類型可以被統一成一種通用的叫作s-expression(符號表達式或s-表達式)的數據類型(s代表符號)。像 `42`，`#\c`，`(1 . 2)` ， `#(a b c)` ，`"Hello"`， `(quote xyz)` ， `(string->number "16")`，和 `(begin (display "Hello, World!") (newline))`都是s-表達式。