高階関数を作ってみたかった

動機

昔からrecursive functionの計算を考えるのは好きだったけれど、高階関数はどう考えればよいのか思い付かず。そこで、何か考えられるようになりたいと思い、試し始めた。

言語はSchemeを使うべきなのだろうけれど、わたしのMacbook proにインストールしてあったDr.Schemeが起動できないので、Juliaを使っております。
Juliaもこういう用途にはシンプルに書けるので、たいがいの役には立つようにみえる。(femtolispは使っていない)

ためす

まずは適当な関数を作って、高階関数の雰囲気に慣れることにした。
複数の関数を引数にとって、呼び方の組み合わせを変えるようなのを作ったりしたけれど、すこし動くものがこれ。発狂している。

fb(f)=(x)->f(x(fb))
hb(f)=(x)->f(x)

julia> fb(hb)(hb)
#35 (generic function with 1 method)

これは、fb(f)は引数に関数をとる関数で、その関数にfb自身を与えるなど、意味不明なことをしている。楽しい。
hb(f)はapply(f,x)みたいなもの。

当然、fb(hb)は関数を生み出す関数しか生み出さないので、何かの値が得られるわけではない。

おもしろいのは、fb(hb)(hb)とか、引数をふやしても、同じような関数ができるだけなので、話がすすまない。

何がかわるのかはよくわからない。たぶんトリビアルな気がする。

いろいろやってみたら

fb(f)=(x)->f(x(fb))
hb(g)=fb(hb)(g)

julia> fb(hb)(hb) 
# infinite loop

となった。まあそうか。

関数の順序関係で再帰

そんなこんながあって、再帰の減少していく値として関数を使うことが考えられてきた。

f -> f^2 -> f^3 -> ... -> f^k

で関数の順序として小さくなっていけばrecursionにつかえる。
が、関数定義を書き換えて別の関数定義を作り(これはmacroの仕事か?)
その間の順序関係を定義するのはなかなかむずかしい・・・

単純に、

f -> one -> zero

となるようなfを定義して、上に考えたようなことを書いてみたらこうなった

function decl(f)
  if f==zero; return 0
  elseif f==one; return zero
  else return one end
  println(f(x))
  return (x)->decl(f)
end

step(x) = println(x)

# step is a function in a step
# cntf in 3rd arg is just a counter
# looper in 2nd arg is for loop

# the if in looper2 cah be change to throw
function looper2(step, looper, cntf)
  (x)->begin
        if x<0; return end
        step(x)
        looper(step, looper, decl(cntf))(x-1)
       end
end

julia> looper2(step, looper2, looper2)(3)
3
2
1
0

期待したようにはなっているようだ。

とはいえ、まだまだトリビアル。

おわり

なかなか高階に達しないけれど、関数の定義を変えてrecursionの終了条件にするというのはありうる。
問題は、先にも書いたように、関数fから新しい関数を作り出す部分。
これは、数式処理で微分するようなものを考えればよいのかもしれないが、そういう知識がないので、残念。
n階微分をやって定数になったら終わり、みたいなことだろうか。

もっといろいろ可能性がありそうなので、続けたい。
紫の本をよめばわかるのだろうか・・

プログラミング言語は、構成的なので、野生の関数というのは作れない(はず)。
だから、高階といっても、低階関数から作られるので、自由はないのかなあと思った。
そうでもないような気もしてきた。

(この件続く)