こともなし

晴。
自分としてはわりと早めに起きる。

モーツァルトの弦楽四重奏曲第十四番 K.387 で、演奏はエマーソンSQ。エマーソンSQ は現代的ないいカルテットだな。中庸というか過不足ないというか、バランスの取り方が見事。

モーツァルトのフルート四重奏曲 K.285 & K.285a で、フルートはペーター＝ルーカス・グラーフ。K.285 って小さいけれど名曲だな。

フォーレのバラード op.19 で、ピアノはジャン＝フィリップ・コラール。

ブラームスのクラリネット五重奏曲 op.115 で、クラリネットはデイヴィッド・キャンベル、Bingham SQ。

＃

Ruby を使って再帰でフィボナッチ数列を求めるには、例えばこんな風にできる。

fib = ->(n) {
  return 1 if n == 1 or n == 2
  fib.(n - 1) + fib.(n - 2)
}

puts fib.(20)    #=>6765

ただし、この方法だと、n の値が大きくなるにつれて急速に時間がかかるようになる。例えば、自分のマシンでは n = 40 で 30秒ほどかかる。 n = 50 くらいになると、時間がかかりすぎて求めることはできない。なので、メモ化以外には遅延評価を使うということが考えられ、Ruby は Proc で遅延評価できるのである。ただこれ、やってみると、fib.(n - 1) + fib.(n - 2) を Proc にくるんでもうまくいかない。これが Proc オブジェクトの和になってしまうからな。必要な方だけ遅延評価するということができない。で、これを何とかしようと色いろと長時間考えてみたのだが、結局よくわからなかった。JavaScript なども含め検索もしてみたが、簡単な関数型言語の実装みたいになってしまっている解説くらいしかなく、やはりクロージャを使っての遅延評価では、無理なのではないかしらんと疑っている。うーん。

階乗ならいける。

factorial = ->(n, r) {
  return r if n == 1
  factorial.(n - 1, n * r)
}

puts factorial.(10000, 1)

ならいわゆるスタックオーバーフローになるのに対し、

tail_call = ->(ob) {
  ob = ob.() while ob.instance_of?(Proc)
  ob
}

factorial = ->(n, r) {
  return r if n == 1
  ->{factorial.(n - 1, n * r)}
}

puts tail_call.(factorial.(10000, 1))

と実装すればよい。ここでは関数 factorial が再帰されて呼び出されるとき、再帰する前の関数は不必要になっているため、こういうことができる。関数 tail_call は、その余分な古い関数の情報を捨てているのである。