2009年10月26日月曜日

Haskell のリスト定義はなぜあの形? - 素朴な解釈

空リストって何?

以前、「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 の空リストってどんなイメージ?
  • 要素がないのになぜリスト?
  • なぜ空リストを想定しないとリストを定義できないの?

全て「空リスト」に関連している。

 

素朴に考える

リストと言われイメージするのは、要素が連なっているもののこと。

091025-005

最初に、最小のリストについて考える。もし、リストの要件として、「要素が連なっている」ことが必須であるならば、最小の連なりは二つの要素。

091025-006

これを代数的データ型で定義すると、

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

以前書いたように、こちらの方が扱いが自然な感じがするので、多分この形になったのではないのかな?

 

関連サイト

関連記事