OCaml

練習問題 4.2 高階関数 フィボナッチ数

練習問題 4.2

次の関数 repeat は twice、fourtimes などを一般化したもので、f を n 回、x に適用する関数です。

let rec repeat f n x =
if n > 0 then repeat f (n-1) (f x) else x;;
val repeat : (‘a -> ‘a) -> int -> ‘a -> ‘a = <fun>

これを使って、フィボナッチ数を計算する関数 fib を定義しなさい(以下の … の部分を埋めなさい)。

let fib n =
let (fibn, _) = …
in fibn;;

(* 練習問題 4.2 *)
(* フィボナッチ数列を計算する関数 fib を定義せよ。 *)

let rec repeat f n x =
    if n > 0
    then repeat f (n-1) (f x)
    else x;;

let twice x = x * 2;;
let test1 = repeat twice 5 2 = 64;;

let fib n =
    let (fibn, _) =
        repeat (fun (x, y) -> (x+y, x)) n (0, 1)
    in fibn;;

(*
let rec fib n =
    if n = 1 then 1
    else
        if n = 2 then 1
        else
            fib (n-2) + fib (n-1);;
*)

let test2 = fib 5 = 5;;
let test3 = fib 10 = 55;;