# Reducing a recursively parameterized data type? **URL:** \ **Category:** Learning\ **Tags:** gadt\ **Created:** [March 8, 2025, 10:17pm UTC](https://discuss.ocaml.org/t/reducing-a-recursively-parameterized-data-type/16240 "2025-03-08T22:17:16Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![sporkl](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/sporkl/32/5242_2.png) [@sporkl](https://discuss.ocaml.org/u/sporkl)\ **Post date:** [March 8, 2025, 10:17pm UTC](https://discuss.ocaml.org/t/reducing-a-recursively-parameterized-data-type/16240/1 "2025-03-08T22:17:16Z")
Suppose I have the following tree type: ```auto type _ weirdtree = | Leaf : int -> int weirdtree | Node : ('a weirdtree * 'a weirdtree) -> 'a weirdtree weirdtree ``` Suppose I want to convert the tree into a list: ```auto let rec list_of_weirdtree : 'a . 'a weirdtree -> int list = fun w -> match w with | Leaf n -> [n] | Node (l, r) -> (list_of_weirdtree l) @ (list_of_weirdtree r) ``` This results in the following error, with `Node (l, r)` underlined: ```auto Error: This pattern matches values of type $0 weirdtree weirdtree but a pattern was expected which matches values of type int weirdtree The type constructor $0 would escape its scope ``` Which mostly makes sense to me. But is there a way to get this sort of function to typecheck? Most of the online results I get for the “type constructor would escape its scope” error seem to be solved by using an explicit polymorphic type annotation, but that doesn’t seem to do the trick here. Thank you! ---
**Author:** ![sporkl](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/sporkl/32/5242_2.png) [@sporkl](https://discuss.ocaml.org/u/sporkl)\ **Post date:** [March 8, 2025, 10:28pm UTC](https://discuss.ocaml.org/t/reducing-a-recursively-parameterized-data-type/16240/2 "2025-03-08T22:28:14Z")
Note that it works as expected for a different definition of the `weirdtree` type: ```auto type _ weirdtree = | Leaf : int -> int weirdtree | Node : ('a weirdtree * 'a weirdtree) -> 'a weirdtree ``` (Note the missing `weirdtree` at the end of the last line) But I want to try to encode the height of the tree into the type, hence the difficulty. ---
**Author:** ![vlaviron](https://avatars.discourse-cdn.com/v4/letter/v/ec9cab/32.png) [@vlaviron](https://discuss.ocaml.org/u/vlaviron)\ **Post date:** [March 8, 2025, 10:55pm UTC](https://discuss.ocaml.org/t/reducing-a-recursively-parameterized-data-type/16240/3 "2025-03-08T22:55:37Z")
You need both an explicit polymorphic annotation, for polymorphic recursion, and a locally abstract type (`type a`) for GADT matching. You can neatly combine both using `let rec list_of_weirdtree : type a. a weirdtree -> int list = fun ...`. In fact, it is commonly advised to always use the `type a.` syntax when writing polymorphic type annotations, even if you don’t actually need the locally abstract type. ---
**Author:** ![sporkl](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/sporkl/32/5242_2.png) [@sporkl](https://discuss.ocaml.org/u/sporkl)\ **Post date:** [March 8, 2025, 11:05pm UTC](https://discuss.ocaml.org/t/reducing-a-recursively-parameterized-data-type/16240/4 "2025-03-08T23:05:56Z")
That was it, thank you! I was confused about locally abstract types before but this makes a lot of sense. ---
**Author:** ![sporkl](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/sporkl/32/5242_2.png) [@sporkl](https://discuss.ocaml.org/u/sporkl)\ **Post date:** [March 8, 2025, 11:18pm UTC](https://discuss.ocaml.org/t/reducing-a-recursively-parameterized-data-type/16240/5 "2025-03-08T23:18:54Z")
I do have a follow-up question. If I change the weirdtree definition so that leafs can hold some variable type as follows: ```auto type _ weirdtree = | Leaf : 'a -> 'a weirdtree | Node : ('a weirdtree * 'a weirdtree) -> 'a weirdtree weirdtree ``` Then is there still a way to get the typing of `list_of_weirdtree` to work out? ---
**Author:** ![vlaviron](https://avatars.discourse-cdn.com/v4/letter/v/ec9cab/32.png) [@vlaviron](https://discuss.ocaml.org/u/vlaviron)\ **Post date:** [March 8, 2025, 11:32pm UTC](https://discuss.ocaml.org/t/reducing-a-recursively-parameterized-data-type/16240/6 "2025-03-08T23:32:39Z")
> [@sporkl](#): > > Then is there still a way to get the typing of `list_of_weirdtree` to work out? What would you expect the type of `list_of_weirdtree` to be ? `'a weirdtree -> 'a list` is probably wrong, as you want the content of the leaves, which is not of type `'a` if your tree has at least one node. `'a weirdtree -> 'b list` is wrong too, as you can’t produce a list of any type from any `weirdtree`. Even trying to existentially quantify over `'b` (instead of universally) wouldn’t work, as you wouldn’t be able to type the recursive call. The usual solution is to add a type parameter to `weirdtree`, for instance `('elt, 'height) weirdtree`, where `'elt` is the type of things stored in leaves and `'height` the one that encodes the height of the tree. Then `list_of_weirdtree` would have type `type elt height . (elt, height) weirdtree -> elt list`. ---
**Author:** ![sporkl](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/sporkl/32/5242_2.png) [@sporkl](https://discuss.ocaml.org/u/sporkl)\ **Post date:** [March 8, 2025, 11:38pm UTC](https://discuss.ocaml.org/t/reducing-a-recursively-parameterized-data-type/16240/7 "2025-03-08T23:38:00Z")
> [@vlaviron](#): > > What would you expect the type of `list_of_weirdtree` to be ? That’s what I couldn’t figure out; I was wondering if there’s a way around it. The solution makes sense. Very much appreciated!