高階関数クイズやってみた
高階関数クイズ - 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だと思いました。(^_^;;