module IntPair = struct
  type t = int * int
  let compare = compare
end
module S = Set.Make(IntPair)

let lim = 30

(* Având (a, b) putem face a += b sau b += a. Calculăm mulțimea tuturor
perechilor obținute, fără a depăși o limită dată pentru elementele perechii *)

let succ (a, b) =
  let sum = a + b in
  if sum <= lim then S.singleton (a, a + b) |> S.add (a+b, b)
  else S.empty

(*  în plus, și a -= b, b -= a cu rezultat nenegativ *)
let id = fun s -> s        (* funcția identitate *)
let succ2 (a, b) =
  let sum = a + b in
  let dif = S.empty
            |> (if a >= b then S.add (a-b, b) else id)
            |> (if a >= b then S.add (a, b-a) else id)
  in if sum <= lim then dif |> S.add (a, a + b) |> S.add (a+b, b) else dif

(* mapunion f { e1, e2, ... en } = { e1, e2, ... en } U f(e1) U ... U f (en) *)
let mapunion f set = S.fold (fun el acc -> S.union (f el) acc) set set

let test1 = S.singleton (3, 5) |> mapunion succ |> S.elements
let test2 = S.singleton (3, 5) |> mapunion succ |> mapunion succ |> S.elements
let test3 = S.singleton (3, 5) |> mapunion succ |> mapunion succ |> mapunion succ |> S.elements

(* punct fix pentru functie de pe mulțimi pe mulțimi *)
let rec fix f s = let s' = f s in
                  if S.equal s' s then s' else fix f s'

let toate pereche = fix (mapunion succ) (S.singleton pereche)
let test4 = toate (3, 5)
let toate2 pereche = fix (mapunion succ2) (S.singleton pereche)
let test5 = toate2 (3, 5) |> S.iter (fun (a, b) -> Printf.printf "(%d, %d) " a b)

This document was generated using caml2html