「ANSI Common Lisp」4章読了

特別なデータ構造と題して、リスト以外のデータ構造を扱う。

本章ではLispのほかのデータ構造である、配列(ベクタとストリングを含む)、ストラクチャ、ハッシュ表の使用法を説明する。これらは、リストほど柔軟性はないかもしれないが、高速なアクセスとスペースの節約が可能である。

「高速なアクセスとスペースの節約」が目的ですね。

配列

配列の作成

make-arrayを使う。

* (setf arr (make-array '(2 3) :initial-element nil))
Warning:  Declaring ARR special.

#2A((NIL NIL NIL) (NIL NIL NIL))
* (setf arr (make-array '(2 3)))

#2A((0 0 0) (0 0 0))
* 

僕が使っている環境では、:initial-elementを指定しない場合、0で初期化されるようです。
ただ、訳注にもあるように、環境依存の挙動のため、:initial-elementは指定した方が良さそうです。

また、#na(nは次元数)を使っても定義できます。

* #2a((b 0 0) (0 0 0))

#2A((B 0 0) (0 0 0))
* 

ちなみに、

Common Lispにおける配列は少なくとも7次元までは大丈夫で、各次元は少なくとも1023の要素がもてる。

そうです。
そういえば、C#にも多次元配列ってあったなあと思って、7次元とかいけるのか試してみた。

using System;

class test
{
        public static void Main(string[] args)
        {
                int[,,,,,,] test = new int[1,2,3,4,5,6,7];

                Console.WriteLine(test.Length);
        }
}

結果はこう。

5040

Lengthプロパティを参照すると、全体のサイズ(各次元の長さを掛け合わせた数)が返ってくるんですね。
Javaとかの感覚だとちょっと違和感あります。

配列の参照と値のセット

arefとsetfを使う。

* (aref arr 0 0)

0
* (setf (aref arr 0 0) 'B)

B
* (aref arr 0 0)

B
* 

ベクタ

1次元配列のことをベクタと特別に呼ぶらしい。

* (setf vec (make-array 4 :initial-element nil)) 
; 
Warning:  Declaring VEC special.

#(NIL NIL NIL NIL)
* (aref vec 0)

NIL
* (setf (aref vec 0) 'B)

B
* (aref vec 0)

B
* (svref vec 0)
; 
B
* 

arefの替わりにsvrefも使えるそうです。(こっちの方が早いらしい)

ストリング

* (typep "abc" 'string)

T
* (typep "abc" 'vector)

T
* (typep "abc" 'sequence) 

T
* 

こんな感じらしい。

ストリングの場合は、arefの変わりにcharを使うらしい。

* (setf str "abc")

Warning:  Declaring STR special.

"abc"
* (char str 0)

#\a
* (setf (char str 0) #\d)

#\d
* str

"dbc"
* 

文字列の比較はequalを使う。大文字・小文字を意識したくない場合は、string-equalを使う。

* (equal "fred" "fred")

T
* (equal "fred" "Fred")

NIL
* (string-equal "fred" "Fred")

T
* 

シークエンス

リスト、ベクタ、ストリングなどの上位概念にあたるらしい。

こんな感じ?
Javaみたいにオブジェクト階層図あったらいいのに。
ちょっと探したけど見つかりませんでした。。

n番目にアクセスする関数の一覧

-	関数名	使いかた例	結果
リスト	nth	(nth 1 '(a b c))	B
配列	aref	(aref (make-array '(2 3) :initial-element nil) 0 0)	nil
ストリング	char	(char "abc" 1)	#\b
ベクタ	svref	(svref (make-array 2 :initial-element nil) 1)	nil
シークエンス	etl	(elt "abc" 1)	#\b

nthだけ引数の順番が逆なのですね。なんか気になる。。

シークエンスの中から特定の要素を探す関数がいくつか紹介されている。

-	動作	使いかた例	結果
position	シークエンス中で指定要素が見つかった場所(ゼロオリジン)を返す	(position 'b '(a b c))	1
position-if	シークエンス中で指定関数を満たす要素の場所(ゼロオリジン)を返す	(position-if #'oddp '(1 2 3))	0
member	シークエンス中で指定要素が見つかった以降のシークエンスを返す	(member 'b '(a b c))	(B C)
member-if	シークエンス中で指定関数を満たす要素以降のシークエンスを返す	(member-if #'oddp '(1 2 3))	(1 2 3)
find	シークエンス中で指定要素が見つかった場合、その要素を返す	(find 'b '(a b c))	B
find-if	シークエンス中で指定関数を満たす要素を返す	(find-if #'oddp '(1 2 3))	1

いずれも、見つからない場合はnilが返ってきますね。

reduce関数

最近話題の(?)MapReduceアルゴリズムのやつかと思ったら、そうでもないらしい?

概念的には、

(fn (fn (fn 'a 'b) 'c) 'd)

を

(reduce #'fn '(a b c d))

と置き換えられるようにする関数のようです。

リストの中でもっとも大きい数値を返す関数をreduceで書いてみる。

(reduce #'max '(1 3 2 5 4))

結果はこう。

* 
5
* 

なんかカッコイイなあ。Lispっぽい感じがします。
RubyではEnumerable#injectってのがあるみたいですね。
Haskellではfoldlが対応するようです。
ってか、名前違い過ぎ。。

main = print $ foldl max 0 [1,3,2,5,4]

結果はこう。

5

ストラクチャ

ストラクチャ(構造体)は、ベクタの豪華版と考えることが出来る。

ですが、まあいわゆるCの構造体のことだと思ってみる。

; 構造体を定義
(defstruct point
  x
  y)

; インスタンス生成
(setf p (make-point :x 0 :y 0))

; 値の参照
(format t "p.x = ~A~%" (point-x p))
(format t "p.y = ~A~%" (point-y p))

; 値の設定
(setf (point-x p) 2)
(setf (point-y p) 3)
(format t "p.x = ~A~%" (point-x p))
(format t "p.y = ~A~%" (point-y p))

; 型のテスト
(format t "(point-p p) = ~A~%" (point-p p))
(format t "(point-p \"str\") = ~A~%" (point-p "str"))

結果はこう。

* 
POINT
* Warning:  Declaring P special.

#S(POINT :X 0 :Y 0)
* p.x = 0
NIL
* p.y = 0
NIL
* 
2
* 
3
* p.x = 2
NIL
* p.y = 3
NIL
* (point-p p) = T
NIL
* (point-p "str") = NIL
NIL
* 

ちなみにHaskellではこんな感じ?

-- 構造体を定義
data Struct = A { x::Int,
                  y::Int } deriving Show

-- インスタンス生成
p :: Struct
p = A 0 0

-- 値の参照、値の設定
main = do print ("p.x = " ++ (show (x p)))
          print ("p.y = " ++ (show (y p)))
          print ("p = " ++ (show p { x = 2, y = 3}))

結果はこう。

"p.x = 0"
"p.y = 0"
"p = A {x = 2, y = 3}"

ハッシュ表

これも最近の言語にはよくあるやつですね。
前の章で、リストをハッシュ的に使うことも出来る例が載ってましたが、最適化のためにデータ構造としても用意されているみたいです。

; ハッシュ表を作ります。
(setf ht (make-hash-table))

; 値をセットします。
(setf (gethash 'cl ht) "Common Lisp"))
(push "Haskell" (gethash 'hs ht))

; 値を参照します。
(format t "ht('cl) = ~A~%" (gethash 'cl ht))
(format t "ht('hs) = ~A~%" (gethash 'hs ht))
(format t "ht('java) = ~A~%" (gethash 'java ht))

; マップの各要素に対してなんらかの処理を行います。
(defun print-map (k v)
  (format t "~A = ~A~%" k v))

(maphash #'print-map ht)

; 値を削除します。
(remhash 'hs ht)

結果はこう。

* Warning:  Declaring HT special.

#<EQL hash table, 0 entries {580142FD}>
* 
"Common Lisp"
* Warning:  Ignoring unmatched close parenthesis.

("Haskell")
* ht('cl) = Common Lisp
NIL
* ht('hs) = (Haskell)
NIL
* ht('java) = NIL
NIL
* 
PRINT-MAP
* CL = Common Lisp
HS = (Haskell)
NIL
* 
T
* 

setfしたのと、pushしたのでは、若干結果が違いますね。(前者はアトムで後者はリスト)

ちなみにHaskellにもHashTableあります。(Data.HashTableモジュール)
が、いまいち使いかた分からず。まあ一応動いてますが、lookupの戻り型(IO (Maybe val))が意味分かりません。。

import Data.HashTable

main = do ht <- fromList hashString [("cl", "Common Lisp"), ("hs", "Haskell")]
          Data.HashTable.lookup ht "cl"

結果はこう。

Just "Common Lisp"