リストを生成するための演算子
Lisp や Scheme を全く知らず Haskell に手を出したとき、そのためか最初に「ん？」と思ったのがリストに対する豊富な操作と重要視。そして、「空リスト」とリストを生成するための演算子 (:) に対する不思議な感覚。どこか何かが腑に落ちなかった。(@_@)
-- []((:), []), -- This is built-in syntax
Syntactic sugar – HaskellWiki に書かれているように、
[1,2,3]is sugar for(1:2:3:[])
リストは (:) のシンタクティックシュガー。
しかし、そもそも (:) って何だろう？と思い型を調べれば、
*Main> :t (:) (:) :: a -> [a] -> [a]
これを見ると、リストを生成するためのデータコンストラクタが (+) のような 2 項演算子と同じようなものとして表現されていることがわかる。
しかし、これは当然のことで、
コンストラクタは特殊な関数にすぎません (ふつうの関数との違いは、パターンマッチで使われるということです)。
先頭にくっつけるのはなぜ？
(:) に戻り、どこに引っかかるものを感じたかと言えば、上記の型にも示されているように、第１引数が要素であり、第２引数がリストであること。
なぜリストの先頭に要素をくっつけるのだろう？ そして、またシンタクティックシュガーの説明にあったように、リストの最後の空リストって結局のところ何だろうか？という疑問が。
「空リストもリストだから (:) 演算子の第２引数として与えることができ、リストの最後に陣取ることができるのだよ」と言われても、「はぁ、そうなんですか…」と思うしかなく、なぜそういう形をしているのかという基本的なところがわからないまま時が過ぎ。
cons (コンス)
随分経ってから「なぜ関数プログラミングは重要か」を読むようになり、その冒頭にリストの定義が書かれていた。(Miranda による記法とのこと。)
listof X ::= nil | cons X (listof X)
ここではじめて cons に出会う。car, cdr については Python をいじっていたときに意識したのだけれど、なぜか cons についてはスルー。Lisp や Scheme を知っているなら、その入門の最初に出てくるはずの関数。^^;
純LISPには二種のデータ(リスト、アトム)、及びそれらを操作する五つの基本関数だけが存在する。…
- car リストの左値をとり出す。(car[(A . B)] -> A)
- cdr リストの右値をとり出す。(cdr[(A . B)] -> B)
- cons 二つの値からなるリストを作る。(cons[A;B] -> (A . B))
- atom 値がアトムならTを返す。(atom[(A B)] -> nil, atom[nil] -> T)
- eq 二つの値が同じ物ならTを返す (eq[A;A] -> T)
とあり、3番目に挙げれている重要な関数。(cf. 最小のLISP も参照)
ん？しかし Lisp では nil はアトムなのか。Structure and Interpretation of Computer Programs によると、
Should nil be an ordinary name? Should the value of nil be a symbol? Should it be a list? Should it be a pair? In Scheme, nil is an ordinary name, which we use in this section as a variable whose value is the end-of-list marker … Other dialects of Lisp, including Common Lisp, treat nil as a special symbol.
とあり、「なぜ関数...」のリスト定義における nil とは異なる。
細かいことはさておき、Scheme – Wikibooks によると、
consはペアを作る手続きです。 (cons 1 2) => (1 . 2)
このペアから無限に続くリストが作れる。リストの終わりを ()という空リストで示すこととすれば、 例えば、1 2 3と続くリストは、 (cons 1 (cons 2 (cons 3 '())))と定義され、 (1 2 3)と表現されます。
ペアを作るのが cons の役割。ペアだからその対象は二つ。
リストとは？
ところで、リストと言えば、「リスト」というものあるとイメージしていた … と言えばいいのかな。Java で言うなら、AraryList, LinkedList…、もちろん自前でオブジェクトをつなげてリストをずるずると作るものも。先頭の要素から後方へリンクを辿っていき、その先に何もなければそこがリストの末尾という認識。上記 Lisp におけるマーカーとしての nil はそれに近いのかな。それに対して、Haskell や上記 Miranda のリスト定義において、「空リストもリストとして定義されている」と言われても何が何だかよくわからず、「ふ～ん、そういものなのか」で済ましていた。
しかし、代数的データ型で定義するということは、
データ型の一種で、他のデータ型を当該代数的データ型のコンストラクタで包んだデータを値とする。
(代数的データ型 – Wikipedia より)
ということであり、空リストもリストというデータ型の値ということになる。リンクを辿っていったら、その先にデータがないというのとは少し事情が異なるようだ。
データコンストラクタは関数
cons - Wikipedia を読むとその冒頭に、
cons (pronounced /ˈkɒnz/ or /ˈkɒns/) is a fundamental function in all dialects of the Lisp programming language.
とあり、cons も関数の一種なんだと改めて認識。
Haskell においても、リストの説明において、
data [a] = [] | a : [a] deriving (Eq, Ord)
リストは、二つの構築子をもつ代数的データ型であるが、3.7 節で述べたように特別な構文をもつ。最初 の構築子は空リストで、`[]' (「ニル」)と書く。二つ目の構築子 は、`:' (「コンス」)と書く。
(cf. Haskell のリストのデータコンストラクタによるパターンマッチ)
ここではじめて (:) を「コンス」と読むのだと知った。^^; 上記の cons の説明と同じく (:) も関数で 2 項演算子。ということは、セクションが使えるはずだと思い試してみると、
*Main> :t (:[2,3]) (:[2,3]) :: (Num a) => a -> [a] *Main> :t (1:) (1:) :: (Num t) => [t] -> [t]
なるほど、今まで (:) を関数と見ていなかったことに気がつかされた。
リストの土台となる cons
さてそのコンス。 cons – Wikipedia によると、
In Lisp, lists are implemented on top of cons pairs.
というように、コンスはリストを作るためのより基本的な構造であることがわかる。
上図を見れば、C や Java でおなじみの一方向リストに見えるけれど、
(cons 1 (cons 2 (cons 3 nil)))
と書かれたのを見た途端に「なぜリストの先頭に要素を追加していくのだろう！？」と疑問を持った。リストなら普通後ろに要素を追加していくのではないの？と。
要素を後ろにつなげていく定義を試してみる
試しに「なぜ関数...」におけるリストの定義を元に、Haskell で要素をリストの後ろに Cons でつなげていく方法を考えると、まず定義を次のように変更する。
data Listof a = Nil | Cons (Listof a) a deriving Show
これで、データコンストラクタが、
Cons リスト 要素
という形になる。これを使ってみると、
main = do print $ Cons (Cons (Cons Nil 1) 2) 3
あれ？ 書きづらい… (@_@;) しかも、リストの先頭に空リストを表わす値 Nil を置くのもどうかと。
データコンストラクタ Cons も関数の一種なので中置記法で書くなら、
print $ Nil `Cons` 1 `Cons` 2 `Cons` 3
うーん、先ほどよりは書きやすいけれど、やはり Nil が先頭なのは微妙…。(+_+)
では、リストの定義を変更して、1 要素でもリストであるとするならば、
data Listof a = El a | Nil | Cons (Listof a) a deriving Show
一つデータコンストラクタが余計に必要になったので冗長… ^^; まぁ、とにかくこれを使ってみると、
main = do print $ Cons (Cons (El 1) 2) 3
先ほどと同じように中置記法を使うなら、
print $ El 1 `Cons` 2 `Cons` 3
折角なのでこれで sum を定義するなら、(import で Prelude の sum を hiding しておく)
sum (El x) = x sum (Cons xs x) = x + sum xs
データコンストラクタで値を生成するときと、パターンマッチで分解するとき
ということで、結局、リストの前に要素を追加するというコンスの構造は、無駄がなく、見た目がリストとして自然な形になるということがわかった。
また、データコンストラクタはパターンマッチに使える特殊な関数であることを考えると、例えば、
sum (x:xs) = x + sum xs
のような定義を見ると、パターンマッチにおいてリストを分解していくとき、「リストの先頭要素と、それ以降のリストをどうしようか？」という視点が持てる。最初にリストの先頭に注目がいくという点が考え方として自然な感じがする。データコンストラクタ (:) は要素を先頭に追加していくということに違和感を覚えたけれど、パターンマッチで分解して考える段になって、それが逆にリストの先頭の方から考えるということになり、リストの見立て方として自然かなと思えた。
いや、そもそも cons というのはリストを生成するための極めて単純な構造体であって、リストという抽象的なものを構成する要素であり、それをリストと同じ抽象レベルで考えるのがおかしいと思えばいいのか。そういえば、リストにリストを追加する関数 (++) は、別に定義されているわけだから、cons でつなげることとリストに要素を追加することは、扱っているレイヤーが違うと考えなくてはいけないのだろう。 cons はあくまでもペアを作る単純な関数であって、それを再帰的に構造化するとリストとして扱うことができると。
再帰的な処理と、リストの再帰的な定義
ところで、リストに対する処理を考えるとき、いきなり「再帰的に問題を考える」と言われても、「そのご神託はどこから来たのだろう？」と不思議だった。確かに言われてみれば、先頭要素とそれ以降のリストとして部分部分に分解できるけれど、それってどういう発想に由来しているのだろうか？と。しかし、それは上記の通り、コンスというリストを支える構造が土台にあり、リストはそれに基いて再帰的に定義してあるので、リストを操作するとき、それを再帰的に処理するという発想は至って自然な流れということになる。
逆に言えば、何らかの構造を生み出すための cons のような関数 (データコンストラクタ) を定義するとき、その再帰的な構造に合わせた要素を処理するための関数を定義することが重要ということ。
新しいデータ型を定義した ときにその型を処理する高階関数を書くべきである。そうすれば、その データ型の取り扱いが簡単になり、その表現の詳細に関する知識を局所化できる。
(なぜ関数プログラミングは重要か より)
とあったのは、結局そういうことなのだろうと理解した。(で、いいのかな？)
cons を一般化したものと考える
ところで、ついでながらここまで来ると「なぜ関数...」において、最初非常に引っかかった reduce の説明も納得がいく。
(reduce f a)を理解する一つの方法は、リストのなかで、consが出現するところをすべてfで置換え、nilが出現するところをすべてaで置換える関数だと看倣すことである。
(「3. 関数の貼り合せ」より)
これを読んだとき、「見做す」って何で (@_@;)？と思った。しかし、そもそも cons は関数の一種であり、要素とリストを取る 2 項演算子と言えるので、見做すもなにも cons 関数で要素をつなげている部分を単に別の関数に置きかえているに過ぎない。以下の図で cons と redece の f の対応をわかりやすく表わされていた。
で、そもそもの話、こういう対応付けができるのは、リストの定義において cons 関数により再帰的な定義がされているためであり、reduce は cons をパラメータ化したものであると考えればよい。(のかな？) リストの定義と reduce を並べてみると、そのことがわかりやすい。
listof X ::= nil | cons X (listof X)
(reduce f x) nil = x (reduce f x) (cons a l) = f a ((reduce f x) l)
どちらで再帰？
最後に、例えば、ごく単純に x ~ y の間の整数を返す ints 関数を定義する。
ints x y
| x <= y = x : ints (x+1) y
| otherwise = []
というように定義できるし、また、
ints x y
| x <= y = ints x (y-1) ++ [y]
| otherwise = []
とも書ける。
それぞれ以下のように、リストの先頭と残りの要素、リストの末尾と残りの要素とに分けて再帰的な定義をしている。
cons のことを考えると、(:) を使って前者のパターンで考えで定義するのが自然に思えてきた。
ちなみに最初のころ、こういう定義を再帰的に見るのではなくて、定義がどのように値に置き換えられていくかという様子から、
ints 1 10 1 : ints 2 10 1 : 2 : ints 3 10 1 : 2 : 3 : ints 4 10
ints というものが右へ移動しつつ何かを残しているように見えたので、これを「うんこぶりぶり」パターンと名付けて関数でリストを返すものは (:) を使うと覚えようとしていた。 ^^;
0コメント:
コメントを投稿