Issue with a tycon mismatch

user_10393957 0
Viewed 155

Working on a homework assignment that essentially takes a tree, the declaration of which is: 

datatype a BinTree = 
Leaf of a
| Node of a BinTree * a BinTree;

and returns a tuple of an int height of tree and a list of values which were stored at that deepest portion of the tree.

fun deepest tree = 
case tree of 
Leaf(n) => [n]
| Node(l, r) => if #1(deepest l) > #1(deepest r) then ((#1(deepest l) + 1), #2(deepest l)) else
                if #1(deepest l) < #1(deepest r) then ((#1(deepest r) + 1), #2(deepest r)) else
                (1, #2(deepest l) @ #2(deepest r));

Trying to test this code, I come up with the following error message: 

stdIn:43.1-47.35 Error: types of rules don't agree [tycon mismatch]
earlier rule(s): 'Z BinTree -> 'Z list
this rule: 'Z BinTree -> [+ ty] * 'Y list
in rule:
Node (l,r) =>
  if (fn <rule>) (deepest <exp>) > (fn <rule>) (deepest <exp>)
  then (<exp> <exp> + 1,(fn <rule>) (deepest <exp>))
  else if <exp> <exp> < <exp> <exp>
       then (<exp> + <exp>,<exp> <exp>)
       else (1,<exp> @ <exp>)
stdIn:21.2-47.35 Error: right-hand-side of clause doesn't agree with 
function result type [type mismatch]
expression:  'Z list
result type:  {1:[+ ty], 2:'X list; 'Y}
in declaration:
deepest =
  (fn tree =>
        (case tree
          of <pat> => <exp>
           | <pat> => <exp>))
stdIn:1.2-47.35 Error: unresolved flex record (need to know the names of ALL 
the fields
in this context)
type: {1:[+ ty], 2:'Y list; 'Z}

While I do understand that its a type conflict, I can't find what the conflict is, nor how to fix it. Any help would be appreciated.

smlnj sml
2 Answers

This

earlier rule(s): 'Z BinTree -> 'Z list

comes from the leaf case ([n]), which makes it a function from trees to lists.

And this:

this rule: 'Z BinTree -> [+ ty] * 'Y list

comes from the node case, making it a function from trees to pairs of "a type that supports addition" and lists.

The remaining errors are caused by SML not being able to deduce what #1 and #2 mean in the presence of that conflict.

Your base case is wrong – it should be a pair, not a list.
The depth in that pair should be 1, and the depth should not be 1 in the case where both subtrees are equally deep.

You're also computing the deepest values three times for each subtree in the worst case, and two in the best case.
It's better to recurse only once for each subtree.

Something like this:

fun deepest (Leaf n) = (1, [n])
  | deepest (Node (l, r)) =
        case deepest l of (dl, ll) =>
        case deepest r of (dr, lr) =>
                      if dl > dr then (dl + 1, ll)
                      else if dr > dl then (dr + 1, lr)
                      else (dl + 1, ll @ lr)
user_4049700

While I also prefer case-of like molbdnilo for writing this function, here is an example of using let-in-end to demonstrate that they can both be used when the result is a product (tuple). Since there are three cases in the if-then-else with three distinct outcomes (dl > dr, dr > dl and dl = dr), using Int-compare may be preferable:

fun deepest (Leaf n) = (1, [n])
  | deepest (Node (l, r)) =
    let val (lcount, ls) = deepest l
        val (rcount, rs) = deepest r
    in case Int.compare (lcount, rcount) of
            GT => (lcount + 1, ls)
          | LT => (rcount + 1, rs)
          | EQ => (lcount + 1, ls @ rs)
    end
user_2359080
Related