# Function same\_shape (t1 : 'a tree) (t2 : 'b tree) gets compiled to same\_shape : 'a tree -\> 'a tree -\> bool **URL:** \ **Category:** Learning\ **Created:** [March 5, 2022, 7:45pm UTC](https://discuss.ocaml.org/t/function-same-shape-t1-a-tree-t2-b-tree-gets-compiled-to-same-shape-a-tree-a-tree-bool/9465 "2022-03-05T19:45:48Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![Linen](https://avatars.discourse-cdn.com/v4/letter/l/d26b3c/32.png) [@Linen](https://discuss.ocaml.org/u/Linen)\ **Post date:** [March 5, 2022, 7:45pm UTC](https://discuss.ocaml.org/t/function-same-shape-t1-a-tree-t2-b-tree-gets-compiled-to-same-shape-a-tree-a-tree-bool/9465/1 "2022-03-05T19:45:48Z")
I’m trying to make a function which compares two [binary trees](https://en.wikipedia.org/wiki/Binary_tree), to see if they have the same shape or not. I created a type `type 'a tree = | Node of 'a * 'a tree * 'a tree | Leaf`. This way I can create a node with a value, and two branches. I then wrote this function: ```auto let rec same_shape (t1 : 'a tree) (t2 : 'b tree) = match t1, t2 with | Leaf, Node(_, _, _) | Node(_, _, _), Leaf -> false | Node(_, x1, y1), Node(_, x2, y2) -> same_shape x1 x2 && same_shape y2 y2 | Leaf, Leaf -> true;; ``` which compiles as ```auto val same_shape : 'a tree -> 'a tree -> bool = ``` The problem is when I try to compare an `int tree` with a `string tree`, I get the following error ```auto Error: This expression has type string but an expression was expected of type int ``` I’m pretty sure that this is because the function is compiled as `'a tree -> 'a tree -> bool`, but I do not want the node value to matter. So my question is, how can I write my function as a `'a tree -> 'b tree -> bool` function? ---
**Author:** ![yawaramin](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/yawaramin/32/3384_2.png) [@yawaramin](https://discuss.ocaml.org/u/yawaramin)\ **Post date:** [March 5, 2022, 8:02pm UTC](https://discuss.ocaml.org/t/function-same-shape-t1-a-tree-t2-b-tree-gets-compiled-to-same-shape-a-tree-a-tree-bool/9465/2 "2022-03-05T20:02:53Z")
Hi, OCaml infers types according to the implementation. In this case it unified the `'a` and the `'b` types into a single type because it saw that the implementation is treating them as the same type. This means you have a bug in your implementation. Check this: `same_shape y2 y2` Just to be clear, the annotationsof `(t1 : 'a tree) (t2 : 'b tree)` were actually ignored during the typechecking process. If you want annotations that will actually cause a type error, use an interface (either a file or a signature). E.g., ```auto module M : sig val same_shape : _ tree -> _ tree -> bool end = struct let rec same_shape t1 t2 = match t1, t2 with | Leaf, Node (_, _, _) | Node (_, _, _), Leaf -> false | Node (_, x1, y1), Node (_, x2, y2) -> same_shape x1 x2 && same_shape y1 y2 | Leaf, Leaf -> true end ``` ---
**Author:** ![Chet\_Murthy](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/chet_murthy/32/1501_2.png) [@Chet\_Murthy](https://discuss.ocaml.org/u/Chet_Murthy)\ **Post date:** [March 5, 2022, 8:50pm UTC](https://discuss.ocaml.org/t/function-same-shape-t1-a-tree-t2-b-tree-gets-compiled-to-same-shape-a-tree-a-tree-bool/9465/3 "2022-03-05T20:50:04Z")
I wondered, reading your explanation, if that was all there was to it. So … ```auto # let rec same_shape : 'a 'b .'a tree -> 'b tree -> bool = fun t1 t2 -> match t1, t2 with | Leaf, Node(_, _, _) | Node(_, _, _), Leaf -> false | Node(_, x1, y1), Node(_, x2, y2) -> same_shape x1 x2 && same_shape y2 y2 | Leaf, Leaf -> true;; val same_shape : 'a tree -> 'b tree -> bool = ``` The only change was to put the type-constraint on the recursive function definition directly. So even if one intended the bug you found, you could still get the indifference to the node-type. Obviously this isn’t the right way to do it, and the natural way is the one that will expose the bug. ---
**Author:** ![octachron](https://avatars.discourse-cdn.com/v4/letter/o/49beb7/32.png) [@octachron](https://discuss.ocaml.org/u/octachron)\ **Post date:** [March 6, 2022, 11:20am UTC](https://discuss.ocaml.org/t/function-same-shape-t1-a-tree-t2-b-tree-gets-compiled-to-same-shape-a-tree-a-tree-bool/9465/4 "2022-03-06T11:20:12Z")
> [@yawaramin](#): > > Just to be clear, the annotationsof `(t1 : 'a tree) (t2 : 'b tree)` were actually ignored during the typechecking process. The annotation is not ignored during typechecking, it is just perfectly valid to infer that `'a = 'b` from the call to ```ocaml same_shape y1 y2 ``` It is the issue with unification type variables which have a semantics that is not well adapted for debugging purpose. Locally abstract types are a better fit than unification variables for such purpose. For instance, ```ocaml let same_shape (type a b) = let rec same_shape (t1 : a tree) (t2 : b tree) = match t1, t2 with | Leaf, Node(_, _, _) | Node(_, _, _), Leaf -> false | Node(_, x1, y1), Node(_, x2, y2) -> same_shape x1 x2 && same_shape y2 y2 | Leaf, Leaf -> true in same_shape ``` fails with ```auto 6 | | Node(_, x1, y1), Node(_, x2, y2) -> same_shape x1 x2 && same_shape y2 y2 ^^ Error: This expression has type b tree but an expression was expected of type a tree Type b is not compatible with type a ``` ---
**Author:** ![Linen](https://avatars.discourse-cdn.com/v4/letter/l/d26b3c/32.png) [@Linen](https://discuss.ocaml.org/u/Linen)\ **Post date:** [March 6, 2022, 12:16pm UTC](https://discuss.ocaml.org/t/function-same-shape-t1-a-tree-t2-b-tree-gets-compiled-to-same-shape-a-tree-a-tree-bool/9465/5 "2022-03-06T12:16:36Z")
Ok, after doing some testing, I’m even more confused. I rewrote the function, and it magically worked. Does anyone know what I did differently? Rewritten function: ```auto let rec same_shape' (t1 : 'a tree) (t2 : 'b tree) = match t1, t2 with | Leaf, Node(_, _, _) | Node(_, _, _), Leaf -> false | Node(_, x1, y1), Node(_, x2, y2) -> same_shape x1 x2 && same_shape y2 y2 | Leaf, Leaf -> true;; val same_shape' : 'a tree -> 'b tree -> bool = ``` Also, thanks for all the help so far. This is still an odd language to me, so this really helps. ---
**Author:** ![hbr](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/hbr/32/4813_2.png) [@hbr](https://discuss.ocaml.org/u/hbr)\ **Post date:** [March 6, 2022, 12:25pm UTC](https://discuss.ocaml.org/t/function-same-shape-t1-a-tree-t2-b-tree-gets-compiled-to-same-shape-a-tree-a-tree-bool/9465/6 "2022-03-06T12:25:38Z")
Did you notice that there is a typo in your function: You probably wanted to write ``` same_shape y1 y2 ``` instead of ``` same_shape y2 y2 ``` Your version forces the compiler to set `'a = 'b` i.e. `'a` and `'b` must be the same type. Otherwise the code is not type correct for the compiler. Regards Helmut ---
**Author:** ![Linen](https://avatars.discourse-cdn.com/v4/letter/l/d26b3c/32.png) [@Linen](https://discuss.ocaml.org/u/Linen)\ **Post date:** [March 6, 2022, 12:50pm UTC](https://discuss.ocaml.org/t/function-same-shape-t1-a-tree-t2-b-tree-gets-compiled-to-same-shape-a-tree-a-tree-bool/9465/7 "2022-03-06T12:50:20Z")
Ah… I feel dumb now. Thanks a lot! ---
**Author:** ![yawaramin](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/yawaramin/32/3384_2.png) [@yawaramin](https://discuss.ocaml.org/u/yawaramin)\ **Post date:** [March 6, 2022, 4:11pm UTC](https://discuss.ocaml.org/t/function-same-shape-t1-a-tree-t2-b-tree-gets-compiled-to-same-shape-a-tree-a-tree-bool/9465/8 "2022-03-06T16:11:25Z")
> [@yawaramin](#): > > This means you have a bug in your implementation. Check this: `same_shape y2 y2` Just fyi, that’s what I said earlier 😉 ---
**Author:** ![Chet\_Murthy](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/chet_murthy/32/1501_2.png) [@Chet\_Murthy](https://discuss.ocaml.org/u/Chet_Murthy)\ **Post date:** [March 6, 2022, 7:08pm UTC](https://discuss.ocaml.org/t/function-same-shape-t1-a-tree-t2-b-tree-gets-compiled-to-same-shape-a-tree-a-tree-bool/9465/9 "2022-03-06T19:08:59Z")
The glories of code review!