Objective Caml 入門 手習い（5章）その5

ようやく5章が終わりました。

• Objective Caml 入門

Exercise 7,8

問題

Exercise7 与えられた自然数 r に対して x2 + y2 = r であるような， (x,y) (ただし x ≥ y ≥ 0)の組を全てリストとして列挙する関 数 squares r を定義せよ．(検算用資料: r = 48612265 の時 32 個の解 があるそうです．)
Exercise8 map の定義は末尾再帰的ではないため，入力リストの長さが長くなるとそれ に比例した量のメモリ(スタック)が必要になる．map と同機能で，必要な メモリ量が定数オーダーである map2 を定義せよ．(ヒント: 末尾再帰的 (iterative) な関数を使う．)

自分の答え

(* Exercise 7 *)
let squares r =
  let sqr x = x * x in
  let rec squares_ x y l =
    match x, y with
    | _, y when (sqr y) > r -> l
    | x, y when sqr x + sqr y < r -> squares_ (x+1) y l		
    | x, y when sqr x + sqr y > r -> squares_ (y+1) (y+1) l
    | x, y -> squares_ (y+1) (y+1) ((x,y)::l)
  in
  squares_ 0 0 []
;;

Printf.printf "num of pairs -> %d\n" (List.length (squares 48612265));;


(* Exercise 8 *)
let map2 f l =
  let rec recursive result = function
    | [] -> List.rev result
    | x::xs -> recursive ((f x)::result) xs
  in
  recursive [] l
;;

print_list_d (map2 (fun x -> x*x) [1;2;3;4;5]);;

感想

なんとなく末尾再帰に慣れてきた気がする。