Any Type ('a) Binary Tree Traversal + Print

I’ve been trying to write code to traverse and print any binary tree.

However, static typing makes it really difficult.

Here is my attempt. However, it tells me Error: This expression has type char but an expression was expected of type printable

In the example_tree definition.

I totally understand, ‘a’ for example is a char and not a printable, even though a printable accepts a char.

How would I make it work without explicitely initializing the node with Node(Char('a')...) ?

Here is my code:

(* Traverse a Binary Tree  *)

exception Error of string

type printable =
  | Char of char
  | Int of int
  | Float of float
  | String of string
  | Other

type tree = Leaf | Node of printable * tree * tree

(* Makes it easy to print any type *)
let formatter (arg : printable) : string =
  match arg with
  | Char c -> String.make 1 c
  | Int i -> string_of_int i
  | Float f -> string_of_float f
  | String s -> s
  | _ -> raise (Error "Error - Unknown Type")

let rec pre_order (node : tree) : unit =
  match node with
  | Leaf -> ()
  | Node (value, left, right) ->
      print_string (formatter value ^ ", ");
      pre_order left;
      pre_order right

let example_tree =
  Node
    ( 'a',
      Node ('b', Node ('d', Leaf, Leaf), Node ('e', Leaf, Leaf)),
      Node ('c', Leaf, Node ('f', Node ('g', Leaf, Leaf), Leaf)) )

let () = pre_order example_tree

>Solution :

You can’t have Node ('c', ...). Your current type definition of tree just doesn’t allow it.

If you eliminate the printable and switch to a traversal parameterized by the format function, you can have any type you like inside your nodes. (As in my comment above.)

If you want to stick with printable, you can write a function that builds a tree from a simpler description of the characters in it.