Learning Reason by Building in Reason

Anytime I’m exploring a new language, I like to familiarize myself with it by building something familiar. For me, some go-to examples have always been the quick sort algorithm and binary search trees. These are my favorite because they require knowledge of many features of a language. In this article, I’ll walk through my experience and thoughts with Reason, trying to build out these ideas.

Disclaimer: This is what I do to learn. I’m not saying this is the best way to learn. You do you 😎. I’m also no expert in Reason, so many of my examples may be incomplete or unoptimized.

Building Quicksort

The final product looks like this:

let rec sort = (l: list(int)) =>
List.length(l) > 1
? List.concat([
(sort(List.filter(x => x < List.hd(l), List.tl(l)))),
[List.hd(l)],
(sort(List.filter(x => x >= List.hd(l), List.tl(l))))
])
: l;

I won’t go into how quicksort works for the sake of brevity. Instead, I’ll list my brief thoughts while while writing this (admittedly unoptimized) function.

Thoughts

  • I was very pleased with how types are declared. Declaring types looks similar to how it’s done for JS with tools like Flow or TypeScript — just a colon after the variable. For literals like let a = 1; The type can also be inferred or explicitly defined (like let a: int = 1;).
  • It’s refreshing working with a language with a sound type system. No type checks necessary. If I declare something as a list of int, I can be sure that’s what it is
  • l.length or l.hd isn’t a thing. JavaScript has array functions on the array’s prototype, but Reason doesn’t work like that. If you want to use a List method, you must call it from the List module like List.length(l) and List.head(l). This sounds inconvenient, but it’s much clearer what you’re actually calling. l.length in JavaScript could be an array, string, or any custom object’s method.
  • Only needing to add rec before the function to declare it as a recursive function is easy and also serves as documentation that sort calls itself somewhere.

Building a Binary Search Tree (BST)

All that being said, this example was a little more difficult. We’ll start with the base Node type for my tree (probably the hardest part).

/* (::nodeValue int, ::leftSubtree node, ::rightSubtree node) */type node =
| Node(int, node, node)
| Empty;

For a BST, each node on a tree can either be a leaf and have no children or it can have up to two children. Figuring out the exact type for this wasn’t intuitive for me because I couldn’t find any good examples of an optional type (like flow’s ?node). I’m still not sure if this is the best way to handle optional types in reason, but it worked for me!

Edit: There is an option type that I didn’t know about when I wrote these examples. Thanks, Kyle Goggin!

Note the difference in node and Node. node is a defined type. Node is a constructor. More info on these variants here.

Print

/* Inorder Printing. Prints tree values in ASC order */
/* Prints left child, then right child, then self */
let rec print = (node: node) => {
switch node {
| Node(v, left, right) => {
print(left);
print_int(v);
print_string(", ");
print(right);
}
| Empty => print_string("")
}
};

First up: the switch statement. This is one of Reason’s pattern matching mechanisms. This function accepts a node type argument. That argument, as we saw above, can come in two forms. Either the Empty case or as a Node constructor with three arguments: a value and two other nodes.

The really cool thing about this is that the type is destructured right in the switch, so I can then do whatever I want with v, left, and right.

Find

/* checks if `value` is anywhere in the tree recursively */
let rec find = (node: node, value: int) => {
switch (node){
| Empty => false
| Node(v, l, r) => {
v == value || value < v ? find(l, value) : find(r, value);
}
}
};

Find is really one of a BST’s most beautiful functions. Logically, all it does is check if the current value is what you’re looking for. If it’s not, it just calls itself on the left or right subtree, depending on whether you’re looking for something less or greater than the current node’s value.

Just like print, we have to handle both possible forms of the current node. If it’s empty, we know we didn’t find the value so we just return false. If it’s not empty, we check the node value or move on down the tree. I didn’t run into any serious issues with this one. There wasn’t anything new from print.

Insert

/* NOTE: Does not currently check for existing values */
let rec insert = (node: node, value: int) => {
switch(node){
| Node(v, l, r) => {
(value < v)
? Node(v, (insert(l, value)), r )
: Node(v, l, (insert(r, value)));
}
| Empty => Node(value, Empty, Empty);
};
};

To note here, the Empty case is actually very important. It’s the starting point for a new tree. It constructs a new Node from the value passed in. Both of its children are Empty.

The other case (where the node has a value) is similar, it just handles the two children differently. If the value we want to insert is less than the current value we build a new left subtree with the value. If it’s greater, we do the same to the right.

Thoughts

  • If you don’t get your types right, the rest of the process is much more difficult.
  • Variant constructors are very powerful.

Conclusion

Honestly, the hardest part of building these was not having enough code to reference. The language is phenomenal. The toolchain is brilliant. The error messages are clear. I just didn’t have enough examples to view. I found myself looking through the Seattle JS app that Ken Wheeler wrote for examples on how to handle types properly among other things.

For people like myself, I published the examples mentioned here, along with insertion sort and (a very simple) stack implementation on GitHub. Hopefully having these examples available is helpful to anyone learning in the future. I’d love to see Reason used more widely in 2018!

In summary:

I hope this has been helpful! If you liked this article, show it some love or tweet about it! You can also find me on Twitter.

Open Source Engineer @apollographql , maintaining the Apollo CLI & Editor Extensions. Learning & Teaching. Purveying fine memes. Jesus & JavaScript. He/him