Recursive types in OCaml?

Question

Hi this is my first time posting on Stack Overflow and I've run into a problem while trying to construct a type in OCaml

I'm trying to construct a type tree that has nodes/leafs/etc. This is what I have so far.

type ('a, 'b) tree = Empty | Leaf of 'b | Node of ('a * tree) | ....

My node is supposed to be a type that contains the its name and another tree as a tuple. But when I tried to compile this it said tree required two arguments. So I tried:

type ('a, 'b) tree = Empty | Leaf of 'b | Node of ('a * tree ('a*'b))

and I was still getting an error. Anything that you notice I was doing wrong? Thanks!

Answer 1

type ('a, 'b) tree = Empty | Leaf of 'b | Node of 'a * ('a, 'b) tree

You probably want your Nodes two have more than one child, though

type ('a, 'b) tree = Empty | Leaf of 'b | Node of ('a, 'b) tree * 'a * ('a, 'b) tree

PS : Beware than in a type declaration, Foo of bar * baz and Foo of (bar * baz) are not the same : the first is a constructor Foo with two fields, the second has only one field, which is of type (bar * baz).