Source file product.ml

module type Elt = sig
  type t

  val to_string : t -> string
end

module Make (E : Elt) = struct
  type tuple = E.t list
  type t = tuple list

  let list_to_tuple t = t
  let tuple_to_list t = t

  let tuple_to_string t =
    Printf.sprintf "(%s)" (Utils.string_of_list ", " E.to_string t)

  let to_list p = p
  let to_string p = Utils.string_of_list "\n" tuple_to_string p

  let extend_relation value tuples acc =
    List.fold_left
      (fun new_tuples tuple -> (value :: tuple) :: new_tuples)
      acc tuples

  let cartesian_product values tuples =
    List.fold_left
      (fun new_tuples value -> extend_relation value tuples new_tuples)
      [] values

  let rec product_aux arity values tuples =
    if arity = 0 then tuples
    else
      let new_tuples = cartesian_product values tuples in
      product_aux (arity - 1) values new_tuples

  let product arity values =
    let one_ary_tuples = List.map (fun elt -> [ elt ]) values in
    product_aux (arity - 1) values one_ary_tuples

  let fold f start product = List.fold_left f start product
end