Recursive functions & recursive types

1

I’ve been working on bindings for Discord.js, which is an extremely OOP heavy library that contains a lot of circular bindings. The forums lead me to this answer

After reorganizing my types, I’d like to wrap the abstract types into variant types. I prefer the DX variant types give over simple abstract types + getters.

This is what I came up with using recursive functions

I’m not sure how to make a base case for these wrappers so they don’t loop infinitely. I’m stuck with a Maximum call stack size exceeded error

Any help on how to stop mutually recursive functions is appreciated

2

If I understand correctly, the problem comes down to creating two records that mutually link to each other:

type rec a = {b: b}
and b = {a: a}

let a = {b: ???}
let b = {a: a}

I don’t think this is possible without using a mutable field. Here is what I came up with:

type rec a = {b: b}
and b = {mutable a: a}

external makeTmpA: unit => a = "%identity"

let b = {a: makeTmpA()}
let a = {b: b}
b.a = a

Hope this helps.

1 Like
3 
type rec a = {a: b}
and b = {b: a}

let rec a = {a: b}
and b = {b: a}
2 Likes
4

The problem comes down to dependency cycles. I’m not allowed to have a getter function from each module get called. That will create a cycle. So a recursive function was my first attempt at solving.

I might just have to give up on using Variant types when interroping with JS which is a bit sad, but nbd

5

Nice! Didn’t know about this syntax.

If we can make the following assumptions:
guild === guild->getGuildRoleManager->getGuild
roleManager === roleManager->getGuild->getGuildRoleManager

then, I would try something like this to break the loop:

let rec wrapGuild = (guild): Types.guild => {
  ...
  let id = ...
  let name = ...
  let rec result = {
    id: id,
    name: name,
    roles: roles,
  }
  and roles = wrapRoleManager(~guild=result, guild->getGuildRoleManager)
  result
}

and wrapRoleManager = (~guild=?, roleManager): Types.roleManager => {
  ...
  let keys = ...
  let values = ...
  let cache = ...
  let guild = switch guild {
    | None => roleManager->getGuild->wrapGuild
    | Some(x) => x
  }
  {t: roleManager, cache: cache, guild: guild}
}

Or maybe merge wrapGuild and wrapRoleManager into a single function.

But if the above assumptions don’t hold, it will be trickier. One solution that comes to mind is some kind of a cache so you would not wrap a same guild twice. In any case, in order to break the loop there needs to be some condition that ensures that at some point you return without making a recursive call.

6

The fact that you’re getting a stack overflow error suggests to me that the problem isn’t just with how the types or modules are defined. If the input data is recursive (i.e., guild foo contains role manager bar, which contains guild foo again), then the problem becomes a lot trickier.

The exact same kind of issue can happen with very simple types and functions as well. Consider a recursive list:

type wrap = Wrap(int)
let rec wraplist = l =>
  switch l {
  | list{} => list{}
  | list{hd, ...tl} => list{Wrap(hd), ...wraplist(tl)}
  }

let rec l = list{0, ...l} // infinite zeros
wraplist(l) // This will wrap the same 0 over and over until a stack overflow.

There are techniques to work around this (e.g. store converted values in a mutable cache), but if there’s a way you can avoid recursively converting the data in the first place, then that would probably be easier.

2 Likes
7

Can you make one of the types opaque and provide functions for accessing fields?

8

This is what I’m concluding.

While I like Variant types, they might just not be possible exactly the way I want it. JS interop causes a lot of problems. If only we could stay inside rescript

Specifically, having variant types recursively referenced inside variant types. Instead I’ll just store abstract types inside the variants, and wrap them when using them

Like this:

type a = { t: getA(), b: getB() }

type b = { t: getB(), a: getA() }

let useAandB = (a, b) => {
  let wrappedB = a.b -> Variants.wrapB
  let wrappedA = wrappedB.a -> wrapA
}

That way, I won’t need recursive functions at all