高階関数クイズやってみた

高階関数クイズ - Oh, you `re no (fun _ → more)をやってみた。

Ocaml使ったことないんでインストールして試してみる。

# let twice f x = f (f x);;
val twice : ('a -> 'a) -> 'a -> 'a = <fun>
# let add1 x = x + 1;;
val add1 : int -> int = <fun>
# add1 0;;
- : int = 1
# twice add1 0;;
- : int = 2
# twice twice add1 0;;
- : int = 4
# twice twice twice add1 0;;
- : int = 16
# twice twice twice twice add1 0;;
- : int = 65536
# exit;;
- : int -> 'a = <fun>
# 

Ocamlだとよく分からないのでSchemeでもやってみる。

(define ((twice f) x)
  (f (f x)))
; twice
(define (add1 x)
  (+ x 1))
; add1
((twice add1) 0)
; 2
(((twice twice) add1) 0)
; 4
((((twice twice) twice) add1) 0)
; 16
(((((twice twice) twice) twice) add1) 0)
; 65536

このコードでOKそう。

何故、上記のようなことになるのか?
twiceが作用する回数を考えた時、

;; twice を1回作用
(expt 2 1)
; 2

;; twice を2回作用
(expt (expt 2 1) 2)
;4

;; twice を3回作用
(expt (expt (expt 2 1) 2) 2)
; 16

;; twice を4回作用
(expt (expt (expt (expt 2 1) 2) 2) 2)
; 256

となりそうだが、上記コードを実行した場合は以下のようになるため。

;; twice を1回作用
(expt 2 1)
; 2

;; twice を2回作用
(expt 2 (expt 2 1))
; 4

;; twice を3回作用
(expt 2 (expt 2 (expt 2 1)))
; 16

;; twice を4回作用
(expt 2 (expt 2 (expt 2 (expt 2 1))))
; 65536

#もちろん、最初は256だと思いました。(^_^;;