あどけない話

インターネットに関する技術的な話など

Haskellのリスト定義の謎

ghci を起動し、":info []" とタイプすれば、リストの定義が表示されます。

> :info []
data [] a = [] | a : [a]

これが何を意味しているのか、僕は長い間分かりませんでした。同じように悩んでいる人もいるかもしれないので、説明してみます。

まず、第一の分かりにくい点は表記が揺れていることです。リスト型を意味する部分が、= の左側では "[] a"、右側では "[a]" となっています。これはどちらか一方に統一すべきでしょう。ここでは、"[] a" を選んでみます。

data [] a = [] | a : [] a

ちなみに、型の部分に "[a]" と書くと、それは "[] a" の別表現になります。a は型変数です。値の部分に "[a]" と書くと、"a:[]" の構文糖衣です。a は単なる変数です。

第二の分かりにくい点は、データ構成子が二項演算子として使われていることです。"()" で囲んで前に出してみましょう。

data [] a = [] | (:) a ([] a)

第三の分かりにくい点は、data の定義に記号が使われていることです。ユーザが定義するデータ型では、型の部分に記号は使えません。ただ、構成子なら ":" で始まる記号列を使って二項演算子風に書くこともできます。

第四の分かりにくい点は、"[]" が構成子である空リストと型の名前に使われていることです。

型の名前と、構成子を区別がつくようにアルファベットに変えてみましょう。

data List a = Nil | Cons a (List a)

これなら、分かると思います。ちなみに二分木と比べてみましょう。

data Tree a = Leaf | Node a (Tree a) (Tree a)

リストが木の特殊形であることがよく分かりますね。