Haskell演習メモ
無限リストの中身を確認する方法
例えば、
take 100 (repeat 1)
を実行すると、全ての要素が1であるような無限リストの、先頭100要素だけを出力できます。
なお、repeatというのは、引数として受け取った値を全ての要素とするような無限リストを生成する関数です。（ただし、onesの定義にrepeatを使うのは間違いなく推奨されません。再帰的に定義しましょう。）
repeatといった関数は、Preludeと呼ばれる標準で読み込まれるモジュールに含まれています。Preludeのリファレンスの、List operationについての項目を眺めておくと良いと思います。
リスト内包表記
リストを集合っぽく書く方法です。あちこちに色々書かれてますが、リストの内包表記と数列表記の解説が分かりやすいでしょうか。『プログラミングHaskell』（これは地下に投棄してある）とか、『すごいHaskell』とかにも載ってます。
リストの再帰定義
fibsの無限リストとか、なんかかっこいい定義をいきなり思いつくのは中々無理なのでググってみるのが良いと思います。ググらずに自分で定義を書いた後に、ググって出てきたかっこいいのを眺めるのがもっと良いとは思いますが。その後に、なんでこんな定義でいけるのだろうかと考えれば十分でしょう。
とりあえず、リストの先頭が何であるかは分かってないと困ります。次に、先頭要素を取り除いたリストがどうなってるのかも知りたいです。先頭要素を取り除いたリストについても、先頭が何であるかだけを知っていればとりあえず十分です。これでリストの2番目の要素がわかりました。そんな感じで再帰します。
実はこれは、プログラミングで一番普通に使われる構造的再帰というより、余再帰と呼ばれる構造をしています。構造的再帰ではどんどんと値を小さくしてbase-caseに帰着しますが、余再帰ではbase-caseからどんどん値を大きくしていきます（すごく適当な書き方ですみません、わたしも良く分かってません）。iteratorとかgeneratorとか呼ばれるものにも現れる構造です（というか無限リストはiteratorそのものです）。http://en.wikipedia.org/wiki/Corecursionに色々書いてます。
Island Life - 無限素数列、続きからの引用で、
普通のlazyな言語で無限リストを作るには、余再帰と呼ばれる、(lazy-cons <要素> <再帰呼び出し>) というパターンが使われる。上に示したコードもこのパターンになっている。
と書いています。(lazy-cons <要素> <再帰呼び出し>)は、Haskellでは<要素> : <再帰呼び出し>に相当します。
あるいは、情報論理演習にでてきたinductive definitionとも考えられる気がします。再帰的に定義されたリストのことを、集合Aに対して、{<決まった要素> + <Aを使った再帰呼び出しの結果>}を対応させるような関数だと考えて、これが包含関係に対してorder-preservingだったら何かうまいこといく、みたいな感じ。order-preservingにならない例として、{<決まった要素> + <Aに含まれない要素>}を対応させるのを考えたら、ラッセルもびっくりなクレタ人集合だなーとかぼんやり思いました。
実際に再帰呼び出しとして何を書けばいいのかは、漸化式を書いている感じだと捉えられると思います。
自然数のリスト列挙
情報論理演習のalpicolaによるQ03 cの証明とほぼ同じやり方でできたので、聞いてた人は思い出してみると良いと思います。
まず、[[0],[1],[2],...]という無限リストと、[[0,0],[0,1],[1,0],[0,2],[1,1],[2,0],...]という無限リストを結合したりすると、たとえば[0,0]という要素はいつまで経っても取得できなくなって困ります。全ての要素が異なる無限リストってのは自然数との間の全単射みたいなものですが、こんなのは自然数から成る有限長リストと自然数との間の全単射と言えません。
(リストの要素長 + リストに含まれる要素の総和)がn∈Natであるような自然数のリストのリストは、有限の長さしかありません。なので、nを0から増やしながら、このリストを繋げていけば大丈夫です。まあ和がnになるリストを列挙するのも結構厄介な作業ですが、落ち着いて再帰すれば何とかなります。
なお、長さがlのリストで、中に含まれる要素の総和が一定になるようなものを列挙することを繰り返すっていう作業は、Nat^lの上に、[n_1,n_2,...n_i,...n_l]→[n_1,n_2,...n_i+1,...n_l]という推移関係をすべてのiに対して作ったときの、クリーネ閉包を得る手続きと考えられます。同じ事をリスト内包表記あるいはリストモナドでやろうとすると、うまくいきません。深さ優先探索で辿りつけないノードは存在します。深く深く何かにのめりこんでいたら広い世の中のことを全く知ることができない、まるで人生！
さて、Q03の別の証明方法として、自然数との間の全単射の関数を構成してしまうというのが考えられます。NatからNat^2への間の全単射は構成できるので、まずNatから(nがいくらであるか × Nat^nへの全単射を考える自然数)が作る集合への全単射を考えられて、NatからNat^nへの全単射を再帰的に構成すればなんとかできると思います。ですが、リストが自然数との間の全単射であるといっても、無限リストの定義は自然数との全単射を陽に作ることで行われるのではなく、リストに含まれる要素に対して、次の要素が何であるかを示すことで行われます。
もちろんfを全単射として、map f [0..]というふうにすれば可能ですが、それは何だか気持ち悪い定義です。でもこの方法でやってみるのも良い練習になりそうだから、やってみてもいいかも。
ListLike
注目すべきなのは、先頭の値の取り出しがO(1)で行われることは要請されないということです。平衡が取れていないと値の取り出しに時間がかかるけど、平衡取らないなら結合が簡単にできて、かつリストに変換するような関数はOCamlで書かされたデータ構造、誰もが知っているはず…。
自分で定義したデータ型のインスタンスをGHCiに表示
スライドにも書いていますが、
data MyTree a = Node (MyTree a) (MyTree a) | Leaf a deriving Show
のように、deriving Showをつけて書きましょう。
Showって一体何なんだというと、ある型がShowクラスに所属しているならば、その型の値をStringに変換するようなshow関数が存在する、ということを意味しています（実際のShowクラスの定義はもうちょっと複雑だったけど）。そして、deriving Showは、データ型の定義からそれっぽいStringへの変換方法を勝手に導出（derive）させることを意味します。
GHCiである値が表示されるときには、後ろでこのshow関数が呼ばれて文字列に変換された結果が表示されています。なので、deriving showをしないとダメです。
Haskellでは、文字列は文字（Unicodeコードポイント）のリストなので、
take 100 $ show $ repeat 1
とすると、1から始まるような無限リストを文字列で表現した結果の先頭100文字を表示します。遅延評価されるので、show $ repeat 1が無限に終わらないということはありません。
型クラスってなんぞや
OCamlでは同じ名前を持つ複数の関数を定義することはできなかったですが、それを実現するための仕組みです。でもなんでそんな仕組みが必要なんでしょう？
例えば、二分木を作ることを考えると、木に入れる値には線形順序がついていないといけません。線形順序がついているというのは、a->a->Boolという型を持つ比較演算が定義されていて、それらが反射的、推移的、反対称的であることですね。なので、「実際のデータ型は分からないが、とにかくそんな演算が定義されている」ことを型シグニチャの上で示せるようにしてやればいいわけです。
Data.Ordは、そういった比較演算が存在することを表す型クラスです。<=だけでは使いにくいので色々関数が定義されていますが、基本的には<=があれば大丈夫です。反射性や推移性や反対称性を型レベルで表現することはできないので、そこはプログラマーが自力で守らないといけません。Data.Setを見ると、Setに値を追加する関数や、Setに値が入っているか確認する関数は、Ordクラスに所属する型の値を引数として受け取ることが分かります。
そんな便利な型クラスなのですが、困ったこともあります。
例えば、
toEnum 0
とGHCiで実行すると、一見謎のエラーが発生します。一定の区間に入るような整数との一対一対応が存在するような型であることを示す、Enumという型クラスがあって、toEnumは数値を受け取ってEnumクラスに所属する型の値を返す関数です。
たとえば、Charは文字コードと対応させれば一定の区間内の整数と対応します。あるいはBoolは、{0,1}と対応します。
なので、toEnumは一体どの型に対して定義された関数を示しているのか分かりません。
(toEnum 0) :: Bool (toEnum 0) :: Char
などのようにすれば解決します。ただ、型推論が完全でなくなってヤダヤダ何これ気持ち悪い、となるわけです。
ちなみに、OCamlでもこれと同様のSetの定義は行われています。/usr/lib/ocaml/set.mliとか、/usr/lib/ocaml/string.mliとか見ると雰囲気が分かります。
OCamlのモジュールは、値とか型とかをひとまとめにしたコンパイル単位です。なんというか、イメージとしてすごく静的なものです。
(* Stringモジュールはcompare関数を定義しているのでOrderedTypeモジュールと互換性があります *) module StrSet = Set.Make(String)
とするとき、Set.MakeとStringから生成された、StrSetという名前が付いたモジュールは、静的なものとして存在します。StrSet.addという関数は、string型の値を受け取る関数でしかありません。Set.Makeファンクタの上では具体的な型が決定されていなかろうが、別のモジュールを受け取ってプログラムの中で使える値や型を持つモジュールとなるときには、すでに型は完全に決まっちゃってるのです。
OCamlのファンクタは、Type Classが実現しているような多相性を静的に解決するのに使えるのかな、などという気がします。
モナド
ぼくはそんなに高度なこと知ってません。モナドのすべてが良いドキュメントかな。他にWeb上ではWikiBooksのUnderstanding monadsとか。『すごいHaskell』は読んでないので分からないんですけど、多分良いと思います。
個別の例では、本物のプログラマはHaskellを使うの連載に出てるものを見るのも良いと思います（連載タイトルは煽りっぽいけど真に受けなくても良い…）。たとえば「取り出し可能な値」のみを持つListモナドとか。連載の初めの方の記事でも古びてることはそんなに無いし、むしろ基礎的な話が多いので有用かなと思います。Real World Haskellには結構プログラム上での実例あります。