空リストって何？
以前、「Haskell の cons (コンス) - リストを生成するための演算子 (:)」で、リストの定義とその構造を支えている cons について触れた。
これを書いたことすら忘れかけていた今日この頃、「やさしい Haskell 入門」におけるリストの定義を読んでいたら、また素朴な疑問がわいた。(@_@;)
リストも同様に簡単に定義できます。リストの場合は再帰的になっているのが面白いですね。
data [a] = [] | a : [a] -- more pseudo-code
… []は空リストであり、:はリストの中置構築子です。つまり、 [1,2,3]は1:2:3:[]と同等であるはずです。(:は右結合性をもちます。) [] の型は [a] で、 : の型は a->[a]->[a] です。(2.4 組み込みの型は特別な型ではない より)
疑問は次の 3 つ。
- 要素が 0 の空リストってどんなイメージ？
- 要素がないのになぜリスト？
- なぜ空リストを想定しないとリストを定義できないの？
全て「空リスト」に関連している。
素朴に考える
リストと言われイメージするのは、要素が連なっているもののこと。
最初に、最小のリストについて考える。もし、リストの要件として、「要素が連なっている」ことが必須であるならば、最小の連なりは二つの要素。
これを代数的データ型で定義すると、
data List a = TwoElem a a
二つの要素を持つ List a 型の値を生成するには、
TwoElem 1 2
次に、3 つ以上の要素の連なりを表現するには再帰的な定義をする。
data List a = TwoElem a a
| List (List a) a
3 つの要素を持つ List a 型の値を生成するには、
List (TwoElem 1 2) 3
4 つの要素の場合は、
List (List (TwoElem 1 2) 3) 4
見方を変える
ここで、リストを「要素の連なりである」という発想を忘れ、要素を入れる「入れ物」と考えるのであれば、要素が 1つ、要素が 0 の状態を想定したとしても不自然ではない。
data List a = TwoElem a a
| List (List a) a
| OneElem a
| Empty
しかし、この定義は冗長。
なぜなら、リストに要素が一つの状態を表現するのに、
OneElem 1
と書けるけれど、
List Empty 1
で代用できる。よって、データコンストラクタ OneElem は必要ない。
同じように、リストに要素が二つある状態 TwoElem 1 2 は、
List (List Empty 1) 2
で代用できるので、データコンストラクタ TwoElem も不要。
結局残ったのは、
data List a = List (List a) a
| Empty
上記の定義は、要素をリストの後ろに追加していくと解釈できる。要素をリストの後ろに追加していくことと、前に追加していくことは、リストの構造にとって本質的な意味を持たないので、以下のように定義したとしても同じ意味。
data List a = List a (List a)
| Empty
以前書いたように、こちらの方が扱いが自然な感じがするので、多分この形になったのではないのかな？
0コメント:
コメントを投稿