Takeuchi Numberの計算もするたらいまわし関数

竹内先生のたらいまわし関数をコンピュータプログラミング言語処理系のチェック等の目的で使う場合、処理系自体が正しく動いているかどうかのチェックとしては、返す値のチェックだけでは不安があります。計算時間の測定であるていどの傾向はわかりますが、もう少し確実な方法として、同関数を基に定義されている数である竹内数(Takeuchi Number, http://mathworld.wolfram.com/TakeuchiNumber.html )も求めるような関数を作りました。意味(意図)を明確にするために、まずHaskellで示します。

続いてScheme版ですが、ここでは多値と、それを受けるletであるlet-valuesを使っていますので、自作の処理系などの場合はconsとcar, cdrで合成・分解するよう修正します。

ghci での実行例を示します。確認は http://oeis.org/A000651 に示されているものと一致するかどうかを見れば良いでしょう。

*Main> map taraiN [0 .. 8]
[(0,0),(2,1),(3,4),(4,14),(5,53),(6,223),(7,1034),(8,5221),(9,28437)]

実際にこれをやってみて観察しているとわかりますが、遅延評価による省略が効かないため、Takeuchi Numberを得るには値呼びの場合とほぼ同様の計算が必要で(時間が掛かりま)す。