2回適用の組み合わせ方

次のような関数daを考える。

(define ((da f) x)
  (f (f x)))

これが何をする関数なのか、日本語での説明を試みよう。

• fを受け取って、「xを受け取って、xにfを2回適用する関数」を返す関数

「〜を受け取って〜を返す関数」という言い方が入れ子になっていて、ちょっと分かりづらい。
動作例を示そう。

gosh> (define ((da f) x)
        (f (f x)))
da
gosh> (define not-not (da not))
not-not
gosh> (not-not #f)
#f
gosh> (not-not #t)
#t
gosh> (not-not 1)
#t

not-notを適用すると、notを2回適用したのと同じ値が返ってきているのが分かると思う。

もちろん、not-notにdaを適用するのもアリ。notの4回適用になる。
そうやって組み合わせていけば、n個のdaで2ⁿ回適用を作れることが分かると思う。

gosh> (define add1 (pa$ + 1))
add1
gosh> ((da (da (da (da (da (da (da (da (da (da add1)))))))))) 0)
1024

0にadd1が2¹⁰回適用されて、1024が返った。

ところで、da自身にdaを適用することができる。

gosh> (((da da) add1) 0)
4
gosh> (((da (da da)) add1) 0)
16
gosh> (((da (da (da da))) add1) 0)
256
gosh> (((da (da (da (da da)))) add1) 0)
65536
gosh> (((da (da (da (da (da da))))) add1) 0) ; 65536^2 = 4294967296 が返るはずだけど……

n個のdaで、2^2n-1回適用になる。適用回数がどんどん自乗されていって、なかなかアグレッシブ。
さてさて、ここからが本題。実は、これ以上に激しい増え方をする組み合わせ方があるのだ。

gosh> (((da da) add1) 0)
4
gosh> ((((da da) da) add1) 0)
16
gosh> (((((da da) da) da) add1) 0)
65536 ; あれれ？

増え方がちょっとおかしいことに気づいてもらえただろうか。
2⁴=16, 2¹⁶=65536 ということなので、この次に

((((((da da) da) da) da) add1) 0)

とやれば2⁶⁵⁵³⁶となる。
n個のdaで2↑↑n回適用。たぶん最強。