読者です 読者をやめる 読者になる 読者になる

YAMAGUCHI::weblog

土足で窓から失礼いたします。今日からあなたの息子になります。 当年とって92歳、下町の発明王、エジソンです。

Objective Caml 入門 手習い(5章)その5

OCaml

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

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]);;

感想

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