Expressing "associated type"

Greetings everyone.
Being inspired by this beautiful blog post, I was trying to express bindings to web APIs without using include (the approach of rescript-webapi). Something like the following:

module Document = {
  type t<'a> = Dom.document_like<'a>

  @send
  external querySelectorAll: (t<'a>, string) => Dom.nodeList = "querySelectorAll"

  @get
  external body: t<'a> => Dom.element = "body"
}

module Node = {
  type t<'a> = Dom.node_like<'a>

  @send
  external appendChild: (t<'a>, Dom.node_like<'b>) => Dom.node_like<'b> = "appendChild"
}

module Element = {
  type t<'a> = Dom.element_like<'a>

  let asNullHtmlElement: Dom.element => Js.null<Dom.htmlElement> = %raw(`
    function (x) {
      if (x instanceof HTMLElement) {
        return x;
      } else {
        return null;
      }
    }
  `)
  
  let asHtmlElement: Dom.element => option<Dom.htmlElement> = element => {
    element->asNullHtmlElement->Js.Null.toOption
  }
}

module HTMLElement = {
  type t<'a> = Dom.htmlElement_like<'a>

  @get
  external innerText: t<'a> => string = "innerText"
}

This would let you write something like this:


let appendElementToBody: Element.t<'a> => unit = element => {
  document->Document.body->Node.appendChild(element)->ignore

  element
  ->Element.asHtmlElement
  ->Belt.Option.forEach(htmlElement => {
    htmlElement->HTMLElement.innerText->Js.log
  })
}

This approach has a great advantage over using different modules that include all related functions, because if you suddenly change an HTMLElement to a HTMLBodyElement, everything still works fine and you don’t need to change all the occurrences of HTMLElement.function to HTMLBodyElement.function.


Now, the problem.
I would like to express what in Rust is called associated type. I am not an Haskeller, but if I did get it right, a similar approach can be expressed with family types.

The reason I need this (which is a limitation expressed in the blog I mentioned above), is to return a different output type depending on the input type. Let me show you a concrete example.

@val
external document: Dom.htmlDocument = "document"

module Document = {
  type t<'a> = Dom.document_like<'a>

  @send
  external createElement: (t<'a>, string) => ??? = "createElement"
}

As you can see, document is an htmlDocument, but createElement should be available on Document module. createElement should return a Dom.element if t<'a> = Dom.document, a Dom.htmlElement if t<'a> = Dom.htmlDocument.

I tried to use GADT to express this, but (probably because I really don’t know anything about GADT :sweat_smile:) I am not able to express the constraint between the document and the element types. Take the following code, for instance:

type rec createElementOut<'a> =
  | Document(Dom.element): createElementOut<Dom.document>
  | HtmlDocument(Dom.htmlElement): createElementOut<Dom.htmlDocument>

@send
external createElement: (t<'a>, string) => createElementOut<t<'a>> = "createElement"

At this point I am not able to correctly write the eval function for createElementOut:

let eval: createElementOut<'a> => 'b = (type a b, doc: createElementOut<a>): b => {
  switch doc {
  | Document(x) => x
  | HtmlDocument(x) => x
  }
}

With this, you get the error that I am returning Dom.element instead of b. If I omit the local scoped type, I just get the error that Dom.htmlElement is returned where Dom.element is expected (obviously).

I also tried to use two generic types for createElementOut, something like this:

type rec createElementOut<'a, 'b> =
  | Document(Dom.element): createElementOut<Dom.document, Dom.element>
  | HtmlDocument(Dom.htmlElement): createElementOut<Dom.htmlDocument, Dom.htmlElement>

let eval: createElementOut<'a, 'b> => 'b = (type a b, doc: createElementOut<a, b>): b => {
  switch doc {
  | Document(x) => x
  | HtmlDocument(x) => x
  }
}

But then you get an unconstrained type, which means that the implementation is unsound:

let x = document->createElement("div")->eval
//  ^--- This is `'a` instead of `Dom.htmlElement`

Do you know if there is a way to express this idea? I totally understand that trying to bend OCAML (and therefore Rescript) functional approaches to express concepts extremely tied to OOP is not the best, but on the other hand we need to make these two worlds interact, and it would be very nice if we could do that without sacrificing ergonomics.

You’re on the right track with GADTs. One thing to note is that the external createElement is not going to be able to consume or return a variant type (including a GADT). The best thing to do here is handle the variant logic in ReScript and send the payload to the external functions.

type rec createElement<'a> =
  | Document(Dom.document): createElement<Dom.document => Dom.element>
  | HtmlDocument(Dom.htmlDocument): createElement<Dom.htmlDocument => Dom.htmlElement>

@send external createElementUnsafe: ('a, string) => 'b = "createElement"

let createElement:
  type a b. (createElement<a => b>, string) => b =
  (x, s) =>
    switch x {
    | Document(d) => createElementUnsafe(d, s)
    | HtmlDocument(d) => createElementUnsafe(d, s)
    }

If we use this, we can see that it works as expected.

let foo = createElement(HtmlDocument(document), "foo") // type Dom.htmlElement
let bar = createElement(Document(other_document), "bar") // type Dom.element

(As a side note, my createElement<Dom.document => Dom.element> form is essentially the same as your createElementOut<Dom.document, Dom.element>. I just like it because it explicitly shows that we’re using it to define how a function type works.)

For extra credit, we can also write a similar function that doesn’t need to wrap the documents in the variant (and avoid allocating a JS object).

type rec createElement2<'a> =
  | Document2: createElement2<Dom.document => Dom.element>
  | HtmlDocument2: createElement2<Dom.htmlDocument => Dom.htmlElement>

let createElement2:
  type a b. (createElement2<a => b>, a, string) => b =
  (x, d, s) =>
    switch x {
    | Document2 => createElementUnsafe(d, s)
    | HtmlDocument2 => createElementUnsafe(d, s)
    }

Which compiles into very clean JS:

function createElement2(x, d, s) {
  return d.createElement(s);
}
7 Likes

Wow! I love it!!!

Thank you so much, you made me realize all my mistakes and misunderstanding about using GADT in this context. As I said, I still need to improve my understandings, and your explanation made me understand where my mental model was totally wrong. :heart:

I love it, it is much clearer than using two generic types as I did.

I will probably use this approach, in the end the type guard is only needed to get the right return type.


I will play a little more with this, I want to try different approaches in order to give a nice usability. If you have any suggestions, feel free to give other (wonderful) ideas :blush:.

@johnj

Really interesting answer, thx !!

  • Can you elaborate on the type a b. notation ? I cannot find it on the docs.

  • And finally, I don’t understand the need for recursion on that variant. (I also did not know that I could type variant’s choices directly).

Can you explain all those point plz ? :slight_smile:

This syntax is for “locally abstract types.” It’s an advanced feature which I don’t think is documented in ReScript yet, but it it works the same way it does in OCaml. (OCaml has documentation on it.)

The basic idea is that normal polymorphic type annotations, like 'a or 'b, aren’t sufficient to express GADTs. type a b. creates new abstract types that exist inside the function body, but appear polymorphic to the outside code.

Recursion is necessary to define GADT variants. In fact, if you remove the rec flag, the compiler gives us a helpful message:

type createElement<'a> =
  | Document(Dom.document): createElement<Dom.document => Dom.element>
  | HtmlDocument(Dom.htmlDocument): createElement<Dom.htmlDocument => Dom.htmlElement>
// ERROR: GADT has to be recursive types, please try `type rec'
1 Like

@johnj

Thx for your explanation, it’s now clear concerning the “locally abstract types”, which is a pretty nice feature indeed :slightly_smiling_face:
I also understood the reason for the recursion, thus my question was wrongly asked.

I realized, that i just don’t know anything about GADT :sweat_smile:
I understand variant, and i love this feature, but now, i try to understand when to recognize the necessecity of using GADT.
Do you have any clue on this subject (ressource, arcticles ?)

PS: I started FP few months ago with the book (Domain Modeling Made Functional) and it was in F#, then i switched to Rescript to stay in the JS Ecosystem. So I’m not an expert in FP and I only know the features available in Rescript from the doc.

GADTs are a very advanced topic, and I’m probably not the best person to explain them. If you’re still learning ReScript (or FP in general), I would probably advise to not worry about them for now. You will very rarely, if ever, need to use them. I’m not even sure that the code in this thread is a great example of how they’re useful.

This is a good explanation of how GADTs work: Type as a value + undocumented (?) syntax - #2 by shulhi

1 Like