作れるので、試してみましょう。順番に出てくる無限リストを構成できます。本質的なところはこれではないはずです。やりたいことはもっと単純なわけで、簡単に表現できていいはずなのです。定義できればよかったはずなのです。定義したことになるはずです!所謂パターンマッチは「データ構造の構成方法に関するマッチ」ですが、今回は「データ構造の分解方法に関するマッチ」なのです。(余パターン)と呼ぶわけなのです。本来ならば関数の挙動を後から定義することなど出来ないはずですが、私達が扱っているのはDataではなくCodataなのです。定義することができるのです。このように全ての分解方法に対して定義を示すことで関数を定義する方法をCoinduction(余帰納法)といいます。余パターンマッチがあると様々な定義をわかりやすく書くことができます。無限リストを表します。いう無限リストを表現できます。書いて良いのでしょうか?**良いのです!**何故ならこれは(余)パターンマッチなのですから。書くように、余パターンもネストしていいのです。余パターンマッチで記述することができます。再帰していることを表します。再帰が停止しなければ定義できたとは言えません。使って見慣れた再帰の形になおしても同じことです。再帰の停止に必要な基底段階の定義が無いのです。停止はせずとも定義は出来ているはずなのです。私達が扱っているのはCodataなので、再帰をしてデータ構造を作り出す過程を無限に行うことができます。対する挙動は明確に示されています。このように、Codataの構造で再帰して新たなCodataを作る書き方をCorecursion(余再帰)といいます。無限に見える書き方にも関わらず、余再帰によって定まる関数は正しく定義されるのです。余再帰的定義から作り出される実際の関数のことをCofixpoint(余不動点)といいます。普通の再帰をCodata上で動かすこともできます。素直な再帰の例ですね。index0​(s)=head(s)indexi+1​(s)=indexi​(tail(s))​ちょっと世界が広がった感じがしませんか。余再帰のおもしろい例として、幅優先探索があります。深さ優先探索は再帰で素直に書けましたよね。幅優先探索は余再帰で素直に書けるのです。幅優先探索することを考えます。普通なら「キューを作って」「一番上のノードを入れて」「子ノードをキューに入れる」というのを無限に繰り返していきます。全要素が既に入ったキューをもう持っているとするのです。この全要素が既に入ったキューというのは勿論無限リストになるわけですから、CoiterationやCopatternで定義ができます。今回はCopatternを使いましょう。構成されたかを見てみましょう。index0​(q)=head(q)=tindex1​(q)=head(flatten(q))=left(head(q))=left(t)index2​(q)=head(tail(flatten(q)))=right(head(q))=right(t)index3​(q)=head(tail(tail(flatten(q))))=head(flatten(flatten(q)))=left(left(q))index4​(q)=right(left(q))index5​(q)=left(right(q))index6​(q)=right(right(q))index7​(q)=left(left(left(q)))​なんだか確かに幅探索していそうですね。返すようにする、という感じです。キューに入っていき、これを無限に繰り返します。実際にプログラムとして動かすことも勿論出来ます。Tree)一応Haskellのコードをおいておきます。幅優先探索は次で定義されます。qsあとは適当に値を抽出するようにするとこんな感じで動きます。ちなみにbfsをちょっと工夫すると、今何段目を探索中であるかなどの情報を付け加えることもできるようになります。行えるような体系でした。普通のDataは分解することが主ですが、Codataでは構築することが主となります。帰納法と余帰納法、パターンマッチと余パターンマッチ、再帰と余再帰は双対なわけです。言うと幅優先探索は深さ優先探索の双対なのかもしれません。今までのwell-knownなデータ構造から双対をうまくとることで新しい世界ができることもあるわけです。everywhere、です。たのしくないですか?おわりにCodataの話だけでも意味のある内容だと思っていますが、実はもっと興味深い内容を含んでいるような気がします。最初に書いた、「データとは操作そのものではないか?」ということです。一般的なプログラミング言語では、操作する対象は実際にメモリなどに存在しているビット列の成すデータでしょう。それは本質ではないのです。私達が本当にやりたかった処理はビット列を操作することではなくデータそのものを解釈し操作することのはずです。実際の表現を知らずとも操作方法さえわかっていればデータを操作することができます。これが抽象化ということです。C言語はダメなんです。あまりにも実表現に近すぎるのです。抽象化ができると主張したところで他の言語には勝てません。C言語で大きなシステムを組むという技術に最早意味はないのです。抽象化というものを学ぶときに一番良いのは数学です。した数学というのは「具象を抽象に持ち上げる」という流れが必ず存在します。抽象の上での操作を具象に映すことで幅広い応用を可能にするのです。プログラミングの流れと大して変わりません。具象がわからないと抽象を理解できないという話をよく聞きますが、それはそれで良いのです。重要なのは「抽象にたどり着くこと」であり、具象の段階で止まってしまうのはもったいないかなと思います。いろんなプログラミング言語は具象の1つであり、その共通構造というものを抽象化して認識することで全てのプログラミング言語が書けるようになる。理想化した話ではありますが、間違った話では無いはずです。抽象化というものや、ものの本質などを考える数学の分野が圏論です。正確に言えば本質を捉えることで概念を統一したり、異なる分野の関連を調べる理論です。今回のCodataの話も圏論で議論することができます。興味があれば覗いてみるといいかもしれません。http://d.hatena.ne.jp/kazu-yamamoto/20121107/1352259739この記事を書いた人phi16Haskellとかレンダリングとか数学とか。