type tree = Known of bool | Unknown of tree * tree
and value = bool option

let string_of_bool = function true -> "1" | false -> "0"

let rec partial_stream prefix n =
  match n, prefix with
    | 0, hd::_ -> hd
    | n, _::tl -> partial_stream tl (n-1)
    | _, [] -> raise Not_found

let find p =
  let rec eval_tree prefix =
    try Known (p (partial_stream (List.rev prefix))) with
      | Not_found ->
          Unknown (eval_tree (false::prefix),
                   eval_tree (true::prefix))
  in
    eval_tree []

let rec print prefix = function
  | Unknown (l,r) -> print (false::prefix) l ; print (true::prefix) r
  | Known v ->
      let prefix = List.rev prefix in
      let prefix = List.map string_of_bool prefix in
      let prefix = String.concat "" prefix in
        Printf.printf "%s.. = %s\n" prefix (string_of_bool v)

let () =
  print [] (find (fun x -> x 2)) ;
  print_newline () ;
  print [] (find (fun x -> x 1 || x 3))

let rec always_true = function
  | Unknown (l,r) -> always_true l && always_true r
  | Known b -> b

let eq p q = always_true (find (fun x -> p x = q x))

let () =
  print_newline () ;
  Printf.printf "eq = %b\n" (eq (fun s -> s 1 || s 10) (fun s -> s 10 || s 1)) ;
  Printf.printf "eq = %b\n" (eq (fun s -> s 1 || s 10) (fun s -> s 10 || s 3))