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)
リストが木の特殊形であることがよく分かりますね。
