unification with recursive datatypes

Following the suggestion to use recursive datatypes for a nested structure like a tree I tried to make said recsurive datatyep work in a test program but encountered (yet another, very cryptic for me) error.

My program is this:

datatype 'a tree =
  Leaf of { value : 'a }
| Node of { value : 'a, left: 'a tree, right: 'a tree }


fun recursivetreebuilder a n =
  if n = 0
  then
      Leaf a
  else
      Node (a, recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1))

So, the function is supposed to build a binary tree of depth n, by recursively calling itself with decremented ns until n is 0.

But I am getting this error:

Can't unify {left: 'a tree, right: 'a tree, value: 'a} with {value: 'b} *
(Int32.int/int -> 'c) * (Int32.int/int -> 'c) (Field 1 missing) Found near if
<( n, 0) then Leaf(a) else Node( a, recursivetreebuilder( ...), ......)

Using recursive datatypes was intended to solve another unification issue when using nested lists. Maybe I should be able to see where the problem is given the explanation to my other question, but I don't yet.

What "Field 1" is the compiler referring to and why can't it unify when recursive datatypes was intended to make it be able to unify different "sub-types" of the same datatype?

Edit

Tried several of the suggested structures, but still getting errors. For example for

datatype 'a tree =
     Leaf of 'a
     |  Node of 'a tree * 'a tree


fun recursivetreebuilder a n =
  if n < 0
  then
      Leaf (a)
  else
      Node (recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1))

I get

val printList = fn : Int.int list -> unit
Error- in 'recon_bintree.sml', line 12.
Can't unify 'a with 'a * Int32.int/int (Type variable to be unified occurs in type) Found near if
<( n, 0) then Leaf(a) else
Node( recursivetreebuilder( a, ...), recursivetreebuilder( ...))
Error- in 'recon_bintree.sml', line 12.
Can't unify 'a with 'a * Int32.int/int (Type variable to be unified occurs in type) Found near if
<( n, 0) then Leaf(a) else
Node( recursivetreebuilder( a, ...), recursivetreebuilder( ...))
Error- in 'recon_bintree.sml', line 12.
Can't unify 'a tree with Int32.int/int -> 'b (Incompatible types) Found near if
<( n, 0) then Leaf(a) else
Node( recursivetreebuilder( a, ...), recursivetreebuilder( ...))
Error- in 'recon_bintree.sml', line 12.
Can't unify 'a tree with Int32.int/int -> 'b (Incompatible types) Found near if
<( n, 0) then Leaf(a) else
Node( recursivetreebuilder( a, ...), recursivetreebuilder( ...))
Exception- Fail "Static errors (pass2)" raised

Solution

There are two problems here.

The first problem is that — for example — { value : 'a, left: 'a tree, right: 'a tree } is a record type, whereas (a, recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1)) is a tuple rather than a record. So they don't match; it's just like passing a real to a function expecting an int.

(Pedantic aside: technically tuples actually are records, but very specific ones; (a, b, c) is syntactic sugar for { 1 = a, 2 = b, 3 = c }. For most practical purposes, you can just think of tuples and records as two similar-but-completely-separate ways to combine types. But now you know why the error-message referred to "Field 1".)

The second problem is that you're declaring the function to use currying (fun recursivetreebuilder a n = ...), but then you try to call it with a tuple (recursivetreebuilder(a, n-1)).

One approach is to stick with your datatype definition, and keep the function using currying, and change everything to match those decisions:

datatype 'a tree =
  Leaf of { value : 'a }
| Node of { value : 'a, left: 'a tree, right: 'a tree }

fun recursivetreebuilder a n =
  if n = 0
  then
      Leaf { value = a}
  else
      Node { value = a,
             left = recursivetreebuilder a (n-1),
             right = recursivetreebuilder a (n-1) }

or change your datatype definition to eliminate the record types, and change the function to eliminate the currying:

datatype 'a tree =
  Leaf of 'a
| Node of 'a * 'a tree * 'a tree

fun recursivetreebuilder (a, n) =
  if n = 0
  then
      Leaf a
  else
      Node (a, recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1))

or mix-and-match the above. (The fix for the record-vs.-tuple problem is independent of the fix for the currying-vs.-tuple problem.)

Incidentally, I think it's a mistake to include a value both in the Leaf case and in the Node case. With your current definition, it's impossible to have a tree containing exactly 0 or exactly 2 elements.

Instead, I think you should either have empty leaves:

datatype 'a tree =
  Leaf
| Node of 'a * 'a tree * 'a tree

or nodes that have child-nodes but no values of their own:

datatype 'a tree =
  Leaf of 'a
| Node of 'a tree * 'a tree

or eliminate the distinction between leaves and nodes, and make the children optional:

datatype 'a tree =
   Node of 'a * 'a tree option * 'a tree option