Search code examples
ocamlbinary-treealgebraic-data-types

Declare tuples in binary trees in OCaml

I understand this is how you define a binary tree type:

type 'a btree = Empty
              | Node of 'a * 'a btree * 'a btree

How would I go about making it a tree of tuples so it has the type ('a, 'b) btree

Solution

  • Well, your first definition defines a tree of any type. So it will work for tuples also.

    # type 'a btree = Empty |Node of 'a * 'a btree * 'a btree;;
type 'a btree = Empty | Node of 'a * 'a btree * 'a btree
# Node ((2,3), Empty, Empty);;
- : (int * int) btree = Node ((2, 3), Empty, Empty)
# Node ((2, true), Empty, Empty);;
- : (int * bool) btree = Node ((2, true), Empty, Empty)

    If you need to enforce tuples in the nodes, you can define a tree that always contains tuples by replacing 'a with 'a * 'b and 'a btree with ('a, 'b) btree in your definition.