宿題

与えられた自然数 r に対して x2 + y2 = r であるような， (x,y) (ただし x >= y >= 0)の組を全てリストとして列挙する関 数 squares r を定義せよ．(検算用資料: r = 48612265 の時 32 個の解 があるそうです．)

let is_natural x = x = (float_of_int (int_of_float x));;

let rec range from_value to_value = 
    if from_value > to_value then 
    else from_value::(range (from_value + 1) to_value);;

let rec find list r = match list with
    (x::xs) -> let y = sqrt(float_of_int(r - x*x)) in 
                  if (is_natural y) && x > (int_of_float y) then
                     (x,(int_of_float y))::(find xs r)
                  else 
                     (find xs r)
  |  -> [];;

let squares r = let base = sqrt (float_of_int r)
                in
                  let from_value = int_of_float(base) / 2
                  and to_value = int_of_float(base)
                  in
                    find (range from_value to_value) r;;

昼寝をしていたら、fold_rightを使うといいことに気がついたので書き直し。

(* fromからtoまでの数列を生成 *)
let rec range from_value to_value = 
    if from_value > to_value then 
    else from_value::(range (from_value + 1) to_value);;

(* 整数版sqrt *)
let sqrt_int x = int_of_float (sqrt (float_of_int x));;

let f r x xs= let y = sqrt_int(r - x*x) in
              if x > y && (x*x + y*y = r) then
                 (x,y)::xs
              else
                  xs;;

let squares r = List.fold_right (f r) (range 0 (sqrt_int r)) ;;