練習問題 6.13
step 関数をヒントにして、フィボナッチ数を表す無限列を定義しなさい。
fib;;
– : intseq = Cons (1, <fun> )
nthseq 10 fib;;
– : int = 55
問題にある「fib;; -:intseq=Cons(1, <fun>)」ができなかった。下の解答だと、「fib 1;;」となる。つまり、「fib 1;;」とすることで、先頭の値が「1」の無限列ができる。
解答(とりあえず)
(* 無限列の型定義 *)
type intseq = Cons of int * (int -> intseq);;
(* フィボナッチ数 *)
let rec fibo x =
if x < 3 then 1
else
fibo (x-1) + fibo (x-2);;
(* フィボナッチ数の無限列 *)
let rec fib x =
if x < 3 then Cons (1, fib)
else
Cons (fibo(x-1) + fibo(x-2), fib);;
(* n番目のフィボナッチ数 *)
let nthseq n f =
let nthseq_in n (Cons (x, f)) =
if n < 3 then 1
else x
in
nthseq_in n (f n);;
実行例
# nthseq 10 fib;;
- : int = 55
正解はこちら
(* フィボナッチの無限数列 *)
let fib =
let rec f x y = Cons (x, f (x+y)) in
Cons (1, f 1);;
(* n番目の数をもとめる *)
let rec nthseq n (Cons (x, f)) =
if n = 1 then x
else nthseq (n-1) (f x);;
引用元 無限数列
う〜ん、これはちょっとむずかしかった。