練習問題 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);;

引用元 無限数列

う〜ん、これはちょっとむずかしかった。

Tweet