Haskell演習メモ
無限リストの中身を確認する方法
例えば、
take 100 (repeat 1)
を実行すると、全ての要素が1であるような無限リストの、先頭100要素だけを出力できます。
なお、repeatというのは、引数として受け取った値を全ての要素とするような無限リストを生成する関数です。（ただし、onesの定義にrepeatを使うのは間違いなく推奨されません。再帰的に定義しましょう。）
repeatといった関数は、Preludeと呼ばれる標準で読み込まれるモジュールに含まれています。Preludeのリファレンスの、List operationについての項目を眺めておくと良いと思います。
リスト内包表記
リストを集合っぽく書く方法です。あちこちに色々書かれてますが、リストの内包表記と数列表記の解説が分かりやすいでしょうか。『プログラミングHaskell』（これは地下に投棄してある）とか、『すごいHaskell』とかにも載ってます。
リストの再帰定義
再帰定義を行うスタイルとして、多分大きくわけて二通りあります。2のべき乗のリストを考えます。
powTows = powTowsFrom 1 where powTowsFrom n = n : powTowsFrom (n * 2) powTows' = 1 : map (* 2) powTows' -- (* 2)というのは、fun x -> x * 2と同じ
の二通りのスタイルが考えられます。
これはi番目の要素がi-1番目の要素のみに依存しますが、fibsのように、i番目の要素がi-1番目の要素とi-2番目の要素に依存するような場合は、前者のスタイルでは関数を2引数のものに変えることで、後者のスタイルではmapの代わりにzipWithを用いればうまくいきます。onesは要素間の依存関係がないので、0引数の関数、つまり単なる変数で大丈夫ですね:)
どちらのスタイルで書くにせよ、実際にどんな計算式を書くのかは、漸化式を書いている感じだと捉えられると思います。
リストをどう定義するにせよ、とりあえずリストの0番目の要素が何であるかは分かってないと困ります。そして、元のリストから先頭要素を取り除いたリストについても、先頭要素を知りたいです。これでリストの1番目の要素が分かります。リストの1番目の要素を算出するためにリストの0番目の要素を使っても構いません。これを繰り返すように再帰します。
前者の書き方は、プログラミングにおいて一般的に再帰と呼ばれる構造というより、余再帰と呼ばれる構造をしています。再帰ではどんどんと値を小さくして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なのでinductive definitionとして正当です。order-preservingにならない例として、paradox = [x|x <- [0..], x `notElem` paradox]などが考えられます。これが停止したらこわいです…。
自然数のリスト列挙
情報論理演習の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に対して作ったときの、クリーネ閉包を得る手続きと考えられます。リストに0をconsする操作も推移関係として追加してやれば、全ての有限長のリストの列挙もできます。
さて、Q03の別の証明方法として、自然数との間の全単射の関数を構成してしまうというのが考えられます。NatからNat^2への間の全単射は構成できるので、まずNatから(nがいくらであるか × Nat^nへの全単射を考える自然数)が作る集合への全単射を考えられて、NatからNat^nへの全単射を再帰的に構成すればなんとかできると思います。ですが、リストが自然数との間の全単射であるといっても、無限リストの定義は自然数との全単射を陽に作ることで行われるのではなく、リストに含まれる要素に対して、次の要素が何であるかを示すことで行われます。
もちろんfを全単射として、map f [0..]というふうにすれば可能ですが、それは何だか気持ち悪い定義です。でもこの方法でやってみるのも良い練習になりそうだから、やってみてるのも良さそうだと思いました。
追記: 自然数kを2進数として展開して、1000000110100001100→[6,0,1,4,0,2]みたいに連続する0の数を数えてもいけそうです。なんかこんなの見るとアセンブラでnumber of leading zeroを数える命令とかゴリゴリ使って書きたくなってきますねえ。この展開によれば、リスト長とリストの要素の総和がnになるってことはn桁の2進数であることにちょうど対応してるんですね。探索アルゴリズムが2進展開にきっちり対応してるの超かわいい、プリティーでキュート。
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には結構プログラム上での実例があります。