ocaml

module Op = struct
  type t =
    | Plus
    | Minus
    | Mult
    | Div
  [@@deriving enumerate]
end
;;

type node =
  { left : expression
  ; right : expression
  ; op : Op.t
  ; is_bracketed : bool
  }
and expression =
  | Node of node
  | Leaf of int
;;

(* enum functions to generate all possible expression of depth i *)
let rec enum i =
  if i = 0 then [(Leaf 0)]
  else (
    let possible_children = enum (i - 1) in
    List.bind possible_children ~f:(fun left ->
      List.bind possible_children ~f:(fun right ->
        List.bind Op.all ~f:(fun op ->
          List.bind Bool.all ~f:(fun is_bracketed ->
          [Node { left; right; op; is_bracketed }])))))
;;

(* to_str functions *)
let op_to_str = function
  | Op.Plus -> "+"
  | Minus -> "-"
  | Mult -> "*"
  | Div -> "/"
;;

let rec expression_to_str = function
  | Leaf x -> Int.to_string x
  | Node { left; right; op; is_bracketed } ->
    let inside = (expression_to_str left) ^ (op_to_str op) ^ (expression_to_str right) in
    if is_bracketed then
      "(" ^ inside ^ ")"
    else inside
;;

(* finally running *)
utop # enum 2 |> List.map ~f:expression_to_str;;
- : string list =
["0+0+0+0"; "(0+0+0+0)"; "0+0-0+0"; "(0+0-0+0)"; "0+0*0+0"; "(0+0*0+0)";
 "0+0/0+0"; "(0+0/0+0)"; "0+0+(0+0)"; "(0+0+(0+0))"; "0+0-(0+0)";
 "(0+0-(0+0))"; "0+0*(0+0)"; "(0+0*(0+0))"; "0+0/(0+0)"; "(0+0/(0+0))";
 "0+0+0-0"; "(0+0+0-0)"; "0+0-0-0"; "(0+0-0-0)"; "0+0*0-0"; "(0+0*0-0)";
 "0+0/0-0"; "(0+0/0-0)"; "0+0+(0-0)"; "(0+0+(0-0))"; "0+0-(0-0)";
 "(0+0-(0-0))"; "0+0*(0-0)"; "(0+0*(0-0))"; "0+0/(0-0)"; "(0+0/(0-0))";
 "0+0+0*0"; "(0+0+0*0)"; "0+0-0*0"; "(0+0-0*0)"; "0+0*0*0"; "(0+0*0*0)";
 "0+0/0*0"; "(0+0/0*0)"; "0+0+(0*0)"; "(0+0+(0*0))"; "0+0-(0*0)"; ...