バリケンのRuby日記

■ [Ruby] 「再帰的な関数」を手続きオブジェクトにする

以前のエントリで「Rubyでは手続きオブジェクトを使うと関数をオブジェクトにできる」ということを書いたけど、ひとつ問題があるんだよ。

それは「再帰的に定義された関数」をオブジェクトにできないんだ。

たとえば、「nの階乗」を求める関数を再帰的に定義してみるよ。

fact = lambda {|n|
  if n.zero?
    1
  else
    n * fact.call(n - 1)
  end
}

puts fact.call(10)

できたー！と言いたいところだけど、手続きオブジェクトの定義中に自分自身を呼んでるね。これではたとえば次のようなことをするとエラーになっちゃうよね。

fact0 = fact #=>このオブジェクトにfact0というラベルも貼り付ける
fact = nil   #=> factというラベルをはがした！
puts fact0.call(10) #=> factという名前で関数を呼べなくなったので、エラーになる

じゃあ、どうしたらいいのかな？もう一段階外側から手続きオブジェクト化すればいいかな？

fact = lambda {|h|
  lambda {|n|
    if n.zero?
      1
    else
      n * h.call(n - 1)
    end
  }
}

さて、これで変数を使わずに手続きオブジェクトにすることができたけど、これってどうやって再帰的に呼び出せばいいのかな。

呼び出すときにfact.call(fact).call(10)と書けば一見うまくいきそうだけど、n * h.call(n - 1)のところで問題になるよ。このhには、内側の手続きオブジェクト(lambda {|n| ... })じゃなくて外側の手続きオブジェクト(lambda {|h| ... })が渡されちゃうんだ。これじゃあ再帰にならないよ。

じゃあ、中のh.call(n - 1)をh.call(h).call(n-1)と書いたら、うまくh.call(h)に内側の手続きオブジェクトが渡されて再帰手続きになりそうじゃない？

じゃあ、やってみよう！

fact = lambda {|h|
  lambda {|n|
    if n.zero?
      1
    else
      n * h.call(h).call(n - 1)
    end
  }
}

puts fact.call(fact).call(10)

わーい、できた！と言いたいところだけど、この手続きオブジェクトを使うときに、必ずfact.call(fact).call(10)と二回呼び出さないといけないのは不便だよね。じゃあ、手続きオブジェクトを与えたら、手続きオブジェクト自身で評価した結果を返すメソッドを定義して、そのメソッドを使って再帰オブジェクトを生成すればいいかな？

def recursive_maker(func)
  g = func
  return g.call(g)
end

fact = recursive_maker(
  lambda {|h|
    lambda {|n|
      if n.zero?
        1
      else
        n * h.call(h).call(n - 1)
      end
    }
  }
)

puts fact.call(10)

やった！目的達成！ただ、h.call(h).call(n - 1)と二回繰り返しているところが惜しいよね。

h.call(n - 1)と書くと、内側の手続きオブジェクトのhに外側の手続きオブジェクトが渡されちゃうのが問題なんだよね。

recursive_makerを工夫したら、次のように書くことが出来るかな？

def recursive_maker(func)
  g = (funcが再帰処理されるように変更する)
  return g.call(g)
end

fact = recursive_maker(
  lambda {|h|
    lambda {|n|
      if n.zero?
        1
      else
        n * h.call(n - 1)
      end
    }
  }
)

puts fact.call(10)

とりあえず、わかりやすくするためにrecursive_makerの中で直接記述している手続きオブジェクトをfとして外に出すよ。

f = lambda {|h|
  lambda {|n|
    if n.zero?
      1
    else
      n * h.call(n - 1)
    end
  }
}

def recursive_maker(func)
  g = (funcが再帰処理されるように変更する)
  return g.call(g)
end

fact = recursive_maker(f)

puts fact.call(10)

うーん、この方法論だと煮詰まっちゃったね（evalを使う手もあるけど、汎用性がない）。これ以上進展がなさそうだから、とりあえず元の「二回呼んでいるバージョン」に戻るよ。

fact = lambda {|h|
  lambda {|n|
    if n.zero?
      1
    else
      n * h.call(h).call(n - 1)
    end
  }
}

puts fact.call(fact).call(10)

内側の手続きオブジェクトの中で2回呼んでいるところを、次のように書くと（内側にさらに手続きオブジェクトができちゃうけど）少なくとも一番内側の手続きオブジェクトはスッキリするよね。

fact = lambda {|q|
  lambda {|m|
    f = lambda {|h, n|
      if n.zero?
        1
      else
        n * h.call(n - 1)
      end
    }
    f.call(q.call(q), m)
  }
}

puts fact.call(fact).call(10)

fって外に出せそうだよね。

f = lambda {|h, n|
  if n.zero?
    1
  else
    n * h.call(n - 1)
  end
}

fact = lambda {|q|
  lambda {|m|
    f.call(q.call(q), m)
  }
}

puts fact.call(fact).call(10)

あれ？このfって、さっき煮詰まったほうのfと似てるよね。fの呼び出し側を工夫すれば、まったく同じに出来ない？

f = lambda {|h|
  lambda {|n|
    if n.zero?
      1
    else
      n * h.call(n - 1)
    end
  }
}

fact = lambda {|q|
  lambda {|m|
    f.call(q.call(q)).call(m)
  }
}

puts fact.call(fact).call(10)

なるほど、これをさっきの煮詰まったほうに応用すれば、recursive_makerメソッドが完成するんじゃないかな？

f = lambda {|h|
  lambda {|n|
    if n.zero?
      1
    else
      n * h.call(n - 1)
    end
  }
}

def recursive_maker(func)
  g = lambda {|q|
    lambda {|m|
      func.call(q.call(q)).call(m)
    }
  }
  return g.call(g)
end

fact = recursive_maker(f)

puts fact.call(10)

やったあ！これで再帰的な関数も、簡単に手続きオブジェクトにできるね。recursive_makerメソッドを使えば、「nの階乗」だけじゃなくて、その他の再帰的な関数も手続きオブジェクト化することができるよ。

で、ここで定義したrecursive_makerメソッドのことを「Y-Combinator」って呼ぶらしいよ。Y-Combinatorの実装方法はここで書いた方法以外にもいくつかあるみたいだから、興味がある人は調べてみてね。