recursion - unification with recursive datatypes -

following suggestion use recursive datatypes nested structure tree tried make said recsurive datatyep work in test program encountered (yet another, cryptic me) error.

my program this:

datatype 'a tree =   leaf of { value : 'a } | node of { value : 'a, left: 'a tree, right: 'a tree }   fun recursivetreebuilder n =   if n = 0         leaf   else       node (a, recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1)) 

so, function supposed build binary tree of depth n, recursively calling decremented ns until n 0.

but getting error:

can't unify {left: 'a tree, right: 'a tree, value: 'a} {value: 'b} * (int32.int/int -> 'c) * (int32.int/int -> 'c) (field 1 missing) found near if <( n, 0) leaf(a) else node( a, recursivetreebuilder( ...), ......) 

using recursive datatypes intended solve unification issue when using nested lists. maybe should able see problem given explanation other question, don't yet.

what "field 1" compiler referring , why can't unify when recursive datatypes intended make able unify different "sub-types" of same datatype?

edit

tried several of suggested structures, still getting errors. example for

datatype 'a tree =      leaf of 'a      |  node of 'a tree * 'a tree   fun recursivetreebuilder n =   if n < 0         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 'a * int32.int/int (type variable unified occurs in type) found near if <( n, 0) leaf(a) else node( recursivetreebuilder( a, ...), recursivetreebuilder( ...)) error- in 'recon_bintree.sml', line 12. can't unify 'a 'a * int32.int/int (type variable unified occurs in type) found near if <( n, 0) leaf(a) else node( recursivetreebuilder( a, ...), recursivetreebuilder( ...)) error- in 'recon_bintree.sml', line 12. can't unify 'a tree int32.int/int -> 'b (incompatible types) found near if <( n, 0) leaf(a) else node( recursivetreebuilder( a, ...), recursivetreebuilder( ...)) error- in 'recon_bintree.sml', line 12. can't unify 'a tree int32.int/int -> 'b (incompatible types) found near if <( n, 0) leaf(a) else node( recursivetreebuilder( a, ...), recursivetreebuilder( ...)) exception- fail "static errors (pass2)" raised 

there 2 problems here.

the first problem — example — { value : 'a, left: 'a tree, right: 'a tree } record type, whereas (a, recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1)) tuple rather record. don't match; it's passing real function expecting int.

(pedantic aside: technically tuples are records, specific ones; (a, b, c) syntactic sugar { 1 = a, 2 = b, 3 = c }. practical purposes, can think of tuples , records 2 similar-but-completely-separate ways combine types. know why error-message referred "field 1".)

the second problem you're declaring function use currying (fun recursivetreebuilder n = ...), try call tuple (recursivetreebuilder(a, n-1)).

---

one approach stick datatype definition, , keep function using currying, , change match decisions:

datatype 'a tree =   leaf of { value : 'a } | node of { value : 'a, left: 'a tree, right: 'a tree }  fun recursivetreebuilder n =   if n = 0         leaf { value = a}   else       node { value = a,              left = recursivetreebuilder (n-1),              right = recursivetreebuilder (n-1) } 

or change datatype definition eliminate record types, , change function eliminate currying:

datatype 'a tree =   leaf of 'a | node of 'a * 'a tree * 'a tree  fun recursivetreebuilder (a, n) =   if n = 0         leaf   else       node (a, recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1)) 

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

---

incidentally, think it's mistake include value both in leaf case , in node case. current definition, it's impossible have tree containing 0 or 2 elements.

instead, think should either have empty leaves:

datatype 'a tree =   leaf | node of 'a * 'a tree * 'a tree 

or nodes have child-nodes no values of own:

datatype 'a tree =   leaf of 'a | node of 'a tree * 'a tree 

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

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