How do I bind subtyping in ReScript?

1

Here’s an example snippet of TypeScript code modeling a Tree type

enum TreeType {
  Node = 0,
  Leaf = 1,
}

interface Tree {
  type: TreeType;
}

interface Node extends Tree {
  type: TreeType.Node;
  left: Tree;
  right: Tree;
  value: string;
}

interface Leaf extends Tree {
  type: TreeType.Leaf;
  value: string;
}

function createTree(): Tree {
  // some code
}

function isNode(v: Tree): v is Node {
  return v.type === TreeType.Node;
}

function isLeaf(v: Tree): v is Leaf {
  return v.type === TreeType.Leaf;
}

How can I write a binding in ReScript code so that I could operate on the Tree type?

@module("tree")
external createTree: unit => tree = ""

I looked at this example Modelling Interfaces in ReScript where the author is using a module type to model the interface, but it doesn’t seem to work with recursive type (maybe it does but I am not sure how, please let me know if I’m wrong with this).

Here’s another approach that I have in mind

@deriving({ jsConverter: newType })
type treeType =
| Node
| Leaf

type rec tree = {
  @as("type") type_: abs_treeType
} and node = {
  @as("type") type_: abs_treeType,
  left: tree,
  right: tree,
  value: string
} and leaf = {
  @as("type") type_: abs_treeType,
  value: string
}

external treeToNode : tree => node = "%identity";
external treeToLeaf : tree => leaf = "%identity";

@module("tree")
external createTree: unit => tree = ""

With this definition, I can do something like this

let t = createTree()

Js.log(t.type_)

switch treeTypeFromJs(t.type_) {
  | Node => {
    let n = treeToNode(t)
    Js.log(n.left)
  }
  | Leaf => {
    let l = treeToLeaf(t)
    Js.log(l.value)
  }
}

which I’m just using the %identity to cast the type from tree to node or leaf, this seems to work (although it is not type safe), but there are two things that I don’t quite like about it.

One thing is that I have the field type_ repeated over 3 of the struct types and value repeated over both node and leaf type and the compiler is not very happy about it, another thing is that three of these types aren’t really associated as if in the code in TypeScript, where Node and Leaf are the subtype of Tree. The latter isn’t much of an issue but the first one is really bugging me. In that case, what could be a better way to model the subtyping/inheritence and the type casting between them?

2

The idiomatic way to port this type would be:

type rec tree =
| Node(tree, string, tree)
| Leaf(string)

Data structures like this are of course usually generic:

type rec tree<'a> =
| Node(tree<'a>, 'a, tree<'a>)
| Leaf('a)

Functions:

let isNode = tree => switch tree {
  | Node(_, _, _) => true
  | Leaf(_) => false
}

let isLeaf = tree => switch tree {
  | Node(_, _, _) => false
  | Leaf(_) => true
}

Usually, you would traverse the tree using pattern matching directly, or some more powerful traversal function, so you wouldn’t really need isLeaf/isNode.

3 Likes
3

Yup I understand what you mean, maybe I should rephrase, the question should be, how do I writing binding for subtype from TypeScript? Consider the example as a library from TyepScript and I have some function that returns a tree like so

@module("tree")
external createTree: unit => tree = ""

and I want to operate on the tree being returened, how should I define the tree type and the subsequent node and leaf types?

I know I can do something like this, but I’m wishing to do it in a type safe manner.

@deriving({ jsConverter: newType })
type treeType =
| Node
| Leaf

@module("./tree.js")
external createTree: unit => 'a = "createTree"

let t = createTree()

Js.log(t["type"])

switch treeTypeFromJs(t["type"]) {
  | Node => {
    Js.log(t["left"])
  }
  | Leaf => {
    Js.log(t["value"])
  }
}

Edit: Updated the question

5

Part of the difficulty of modelling this is that original TS code is missing some type information.

The TS looks like it has 2 types:

// .ts

type tree = node | leaf

type leaf = {
  value: string
  left: undefined
  right: undefined
}

type node = {
  value: string
  left: tree
  right: tree
}

In rescript, undefined is not a value, it is instead a variant type of either None or Some(value). Because of this, the tree is actually 1 type with 4 possible combinations of left and right:

// .res

type rec treeFromTSLand = {
  value: string,
  left: option<treeFromTSLand>,
  right: option<treeFromTSLand>,
}

The same representations (ish) in TS:

// .ts

type tree = node | leaf | weirdTreeStateOne | weirdTreeStateTwo

type leaf = {
  value: string
  left: undefined
  right: undefined
}

type node = {
  value: string
  left: tree
  right: tree
}

type weirdTreeStateOne = {
  value: string
  left: undefined // <-- unhandled case
  right: tree
}


type weirdTreeStateTwo = {
  value: string
  left: tree
  right: undefined // <-- unhandled case
}

So, if you’re absolutely sure that your TS code will only ever produce either the leaf type or node type as they’re defined in your example, you could convert it like so:

// .res

type rec treeFromTSLand = {
  value: string,
  left: option<treeFromTSLand>,
  right: option<treeFromTSLand>,
}

// The same solution that Yawar proposed
type rec tree = Leaf(string) | Node(string, tree, tree)

let rec fromTSTree = (tree: treeFromTSLand) => {
  switch (tree.left, tree.right) {
    // node, as defined in our TS 
    | (Some(l), Some(r)) => Node(tree.value, fromTSTree(l), fromTSTree(r))
    // our TS shouldn't produce this, so fallback to leaf
    | (Some(_), None)
    // our TS shouldn't produce this, so fallback to leaf
    | (None, Some(_))
    // leaf, as defined in our TS
    | (None, None) => Leaf(tree.value)
  }
}

Then, you don’t need the isNode or isLeaf functions (as Yawar stated); pattern matching will check the type and perform branching logic in the same statement:

// .res

let doSomethingWithTreeBranch = (tree) => {
  switch tree {
    | Leaf(value) => Js.log2("It's a leaf!", value)
    | Node(value, _l, _r) => Js.log2("It's a node!", value)
  }
}

However, the big difference between using pattern matching (rescript) vs isNode/isLeaf (TS) is the paradigm shift; the TS code determines the type based on a user-defined value, whereas rescript determines the type based on the shape of the data.

Here’s a link to the playground.

1 Like
6

Thanks for the answer, I think I might have oversimplified the example, I’m actually trying to use the Node type from TypeScript. Apparently, there are a lot of interfaces (although I don’t plan to use all) that extend the Node type like the InterfaceDeclaration and the SourceFile which all have different fields, so it’s impossible for me to define a single type that includes all the fields from all these variants.

Besides two possible solutions, to define all of them as records or to use a Js object (which is not type safe), what would be a better solution in this case?