scalaz.Treeとカタラン数。そして代数的データ型とzipperと微分

scalaz scalaprops 数学


1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900・・・
という数列を知ってますか？カタラン数と言うらしいです。


詳しくはwikipediaみるなり、ググるなりしてください

https://ja.wikipedia.org/wiki/%E3%82%AB%E3%82%BF%E3%83%A9%E3%83%B3%E6%95%B0
https://en.wikipedia.org/wiki/Catalan_number



Eugène Charles Catalanさんという人がいたらしいです。

https://en.wikipedia.org/wiki/Eug%C3%A8ne_Charles_Catalan



さて、標題のscalaz.Treeとカタラン数との関係ですが、こういう話好きな人はすでに知ってるのかもしれません？
というかwikipedia(とくに英語版の方が詳しい)には2分木の例で載ってますね。

ちなみに、先に説明しておくと、scalaz.Treeはrose treeなどと呼ばれる、2分木ではなく任意の個数あるものです。

https://en.wikipedia.org/wiki/Rose_tree


さて本題の説明に入ると

  • あるtree: scalaz.Tree[A] があった際に Foldable[Tree].length(tree) でlengthを定義します。
  • 今はTreeの要素の型には感知したくない(形だけ考えたい)のでTree[Unit]としておきます
  • さて、lengthが1のときのTreeの形は何通りありますか？2のときは？3のときは？
  • lengthがn個に一般化したときのTreeの形の数は？どういった数列、数式で表せるでしょう？


みたいな高校か中学の数学で出てきそうな問題を考えます。はい、それの答えがカタラン数のようです。

実際の例として

  • 長さというか要素数が4のときは5通り
  • 5のときは14通り

存在するという例を貼っておきます



カタラン数の式はwikipediaなどに載ってるし、うまく説明書ける気もしないので省略します。


さて、なんでこんなこと考えてるか？というと、例によってscalapropsというテストライブラリを、地道に改善したり、テスト追加してるわけです。


http://xuwei-k.github.io/slides/scalaprops/#1



なので


「scalaprops.Gen[ scalaz.Tree[A] ] は、本当にすべての形のTreeを生成してくれるのだろうか？」


というのが気になるわけですね？しかし


「そもそもTreeのすべての形の数ってどうやって計算するんだ？」


となりますね？それで色々調べてたらカタラン数にたどり着いて、実際にテスト追加しました


https://github.com/scalaprops/scalaprops/commit/0d93902dfa296d8bf8ecb707df10dc39ff99353c


あとでTreeのZipper( scalaz.TreeLoc )などでも似たようなテスト追加するかもしれません。




さて、このあたりに関連する話や、発展形の話として、


「そもそも代数的データ型って代数だから(?)、データ型の種類の数ってわりと数式で簡単に計算できるんだよ」


「(一般化された)zipperは、その代数的データ型(の数式)の微分を考えることと同等なんだよ」


「そのzipperの考え型応用しつつ、scrap your boilerplate組み合わせて、zipper自体をHaskellで自動で生成(ry」


みたいな、面白い話があるわけですが、既に英語でも日本語でもそれなりにわかりやすい資料あるので、今更自分が説明書く必要性があるのかあやしいので、とりあえず今日はそのあたりの資料を最後に貼って終わりにします