# Getting a recursive function to typecheck

**URL:** <https://discuss.ocaml.org/t/getting-a-recursive-function-to-typecheck/14895>\
**Category:** Learning\
**Tags:** type-system\
**Created:** [July 3, 2024, 5:12pm UTC](https://discuss.ocaml.org/t/getting-a-recursive-function-to-typecheck/14895 "2024-07-03T17:12:38Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![giltho](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/giltho/32/3521_2.png) [@giltho](https://discuss.ocaml.org/u/giltho)\
**Post date:** [July 3, 2024, 5:12pm UTC](https://discuss.ocaml.org/t/getting-a-recursive-function-to-typecheck/14895/1 "2024-07-03T17:12:38Z")

</div>

Hello,

I’m fought for a while with a piece of code that would not typecheck, and I’m curious if there’s an obvious way to get it to typecheck.

Take this code:

```ocaml
type tree =
  | Leaf of int
  | Node of (int * tree * tree)

let rec f (g : int -> 'a) tree : 'a =
   match tree with
  | Leaf i -> g i
  | Node (i, l, r) -> if i >= 0 then f g l else f g r

let x = f (fun i -> "s") (Leaf 0)
let y = f (fun i -> i) (Leaf 0)

```

Running this in the playground gives us, as expected,

```ocaml
type tree = Leaf of int | Node of (int * tree * tree)
val f : (int -> 'a) -> tree -> 'a = <fun>
val x : string = "s"
val y : int = 0

```

However, let’s say that I want `f` to call itself with a different `g` than the one passed as argument temporarily. For example:

```ocaml
type tree =
  | Leaf of int
  | Node of (int * tree * tree)

let rec f (g : int -> 'a) tree : 'a =
   match tree with
  | Leaf i -> g i
  | Node (i, l, r) ->
      if (i == 0) then
        let g' i = Leaf i in
        let ret = f g' (Node (12, Leaf(42), Leaf (24))) in
        f g ret
      else
      if i >= 0 then f g l else f g r

let x = f (fun i -> "s") (Leaf 0)
let y = f (fun i -> i) (Leaf 0)

```

Suddenly, this does not type-check anymore, since it infers the following, which is quite inconvenient:

```ocaml
val f : (int -> tree) -> tree -> tree = <fun>

```

Suddenly, the `g` argument must return a `tree`. Is there a way to get this function to keep inferring that `g : int -> 'a` ?

In my current code (which is much more complex, but let’s simplify here), my `g` function is of type  
`int -> ('a, int)` and I only need the int in my internal recursive call, so I create a function g that returns `((), the_thing_I_need)`, and then discard the unit, and it fails to typecheck.  
I did manage to get it to work by doing `let g i = (Obj.magic (), the_thing_I_need)` but it’s not pretty and I’m not even 100% sure it’s safe.

---

<div class="post-metadata">

**Author:** ![sim642](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/sim642/32/3597_2.png) [@sim642](https://discuss.ocaml.org/u/sim642)\
**Post date:** [July 3, 2024, 5:19pm UTC](https://discuss.ocaml.org/t/getting-a-recursive-function-to-typecheck/14895/2 "2024-07-03T17:19:12Z")

</div>

Writing the first line of `f` like this typechecks:

```ocaml
let rec f: type a. (int -> a) -> tree -> a = fun g tree ->

```

**EDIT:** Took me a while to find the documentation for this syntax: [OCaml - Language extensions](https://ocaml.org/manual/5.2/locallyabstract.html#p:polymorpic-locally-abstract).

This also works (more similar to the linked manual section below):

```ocaml
let rec f: 'a. (int -> 'a) -> tree -> 'a = fun g tree ->

```

---

<div class="post-metadata">

**Author:** ![vlaviron](https://avatars.discourse-cdn.com/v4/letter/v/ec9cab/32.png) [@vlaviron](https://discuss.ocaml.org/u/vlaviron)\
**Post date:** [July 3, 2024, 5:20pm UTC](https://discuss.ocaml.org/t/getting-a-recursive-function-to-typecheck/14895/3 "2024-07-03T17:20:45Z")

</div>

See [OCaml - Polymorphism and its limitations](https://ocaml.org/manual/5.2/polymorphism.html#s:polymorphic-recursion) for a longer explanation of the issue.

---

<div class="post-metadata">

**Author:** ![giltho](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/giltho/32/3521_2.png) [@giltho](https://discuss.ocaml.org/u/giltho)\
**Post date:** [July 3, 2024, 5:34pm UTC](https://discuss.ocaml.org/t/getting-a-recursive-function-to-typecheck/14895/4 "2024-07-03T17:34:19Z")

</div>

@sim642 's solution works, thank you!  
I had tried

```ocaml
let rec f (type a) g tree = ...

```

which is thought was vaguely equivalent but that didn’t work

@vlaviron Thank you, I had read this also, but somehow missed that it did give the solution