fusc.ml

(* Dijkstra's fusc function *)
let rec fusc x =
  if x < 2 then x
  else
    let n = x / 2 in
    if x mod 2 == 0
    then fusc n
    else fusc n + fusc (n + 1)

let iota n =
  let rec f x l =
    if x < 1 then l
    else f (x - 1) (x :: l)
  in
  f n []

(* let map = List.map (* but this would be no fun, right? *)*)
let rec map f = function
  | hd :: tl -> (f hd) :: (map f tl)
  | [] -> []

(* This is my wheel.
 * There are many like it, but this one is mine. *)

(* let reduce f a b = List.fold_right f b a *)
let rec reduce f z = function
  | hd :: tl -> f hd (reduce f z tl)
  | [] -> z

let print_list l =
  (* let join = String.concat in *)
  let join s = reduce (fun x y -> x ^ s ^ y) "" in
  print_string ("[" ^ (join "; " l) ^ "]\n")


let () =
  print_list (map string_of_int (map fusc (iota 20)))

let () =
  print_string "[" ;
  List.iter (fun x -> print_int x; print_string "; ")
    (List.map fusc (iota 20)) ;
  print_string "]\n"