Orz日記 by Akio Morita

_ [SAD][Lisp]複数の引数を伴う再帰関数を定義するY-Combinator

Y = With[{core = #},
  With[{procedure = #},
    core[procedure[procedure][##]&]]&[
      With[{procedure = #},
        core[procedure[procedure][##]&]]&]]&;

生成した再帰関数を包むpure functionで、##を 受けとるようにしただけ

アキュムレータを使った再帰関数の例

リストの平均値を求める

avgY = Y[With[{action = #}, Which[
  Length[{##}] < 3, action[#1, 0, 0],
  Length[#1] > 0,   action[Rest[#1], #2 + 1, #3 + First[#1]],
  True,             #3 / #2]&]&];

リストの標準偏差を求める

sigmaY = Y[With[{action = #}, Which[
  Length[{##}] < 4, action[#1, 0, 0,
    Y[With[{action = #}, Which[
      Length[{##}] < 3, action[#1, 0, 0],
      Length[#1] > 0,   action[Rest[#1], #2 + 1, #3 + First[#1]],
      True,         #3 / #2]&]&][#1]],
  Length[#1] > 0,   action[Rest[#1], #2 + 1, #3 + (First[#1] - #4)^2, #4],
  True,                   Sqrt[#3 / (#2 - 1)]]&]&];

最初に平均値を求める部分に avgY相当の無名関数を使っている

_ [SAD][Lisp]factYの末尾再帰への変形

単純な再帰を Y-Combinatorで書いた基本形

factY = Y[With[{action = #}, Which[
  # < 1,  1,
  True,   # * action[# - 1]]&]&];

アキュムレータを導入して、末尾再帰化

factY = Y[With[{action = #}, Which[
  Length[{##}] < 2, action[#, 1],
  #1 < 1,           #2,
  True,             action[#1 - 1, #2 * #1]]&]&];

最初の呼び出し(アキュムレータの初期化)を再帰の外に出した移す

factY = Y[With[{action = #}, Which[
  #1 < 1,           #2,
  True,             action[#1 - 1, #2 * #1]]&]&][#, 1]&;