binary reference tree lookup for ocaml

Question

type exp = V of var
           | P of var * exp
and var = string

I'm building a binary reference tree where the right leaf nodes lookup for the ones on the left leaf nodes, and returns true if all the right leaf nodes match with some left leaf nodes.

let rec ctree : exp * exp -> bool
=fun (e1,e2) -> match e2 with
  | P (x,y) -> match y with
    | P (a,b) -> if (ctree(a,b)) then true else ctree(x,b)
    | V a -> if a=x then true else ctree(e1,y)
  | V x -> e1=x

But here, I'm keep getting error at line 5:

| V a -> if a=x then true else ctree(e1,y)

The e1 here has a type exp, and it should be that way, but the compiler keeps telling me that it should be a type var=string. Also, for line 6,

V x -> e1=x

it's telling me that there should be type var=string instead of e1 again.

Can anyone tell me why it's getting the error?

Jeffrey Scofield Jeffrey Scofield · Accepted Answer · 2015-10-23T05:14:56

When you have two nested match expressions, it's not clear where the nesting ends. You need to use parentheses around the inner match. Something like this might work:

let rec ctree : exp * exp -> bool =
    fun (e1,e2) -> match e2 with
    | P (x,y) ->
        (match y with
        | P (a,b) -> if (ctree(a,b)) then true else ctree(x,b)
        | V a -> if a=x then true else ctree(e1,y)
        )
    | V x -> e1=x

Second, your type for the function is exp * exp -> bool, which says that e1 is of type exp. At the end of the function you have this:

| V x -> e1 = x

Since x is the value of a V constructor, it must be a string. But then e1 = x only makes sense if e1 is a string also.

So, there's a type conflict in your use of e1.

binary reference tree lookup for ocaml

1 Answers