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

Quicksort is normally where I begin. It’s a really beautiful algorithm, and It’s where I go to get familiar with some of the basic data types (int, list, function) and recursion. It’s also a fun challenge to see how short I can make the function without it being disgusting.

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

  • It felt a lot like writing JS. let variable declarations and anonymous arrow functions are very familiar.
  • 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)

BSTs are something that I’ve written about in the past, had to write in C, and feel very comfortable reasoning about (pun intended). They’re great for exploring optional (more complicated) data types as well as branching/conditionals. I tend to stick to implementing only a few methods for BSTs though — usually print, find, and insert (in that order, since they need each other).

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

Just like find, there wasn’t too much new with insert. Just a bunch of Node constructor calls.

/* 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

  • Getting the Node type right was tricky. It took me more than a couple tries to figure out how to make an optional value.
  • If you don’t get your types right, the rest of the process is much more difficult.
  • Variant constructors are very powerful.

Conclusion

Building these examples in Reason was difficult, but I’m surprised by how tough the results are to break. The type safety in reason prevents all kinds of errors. Reason’s new syntax makes it seem similar enough to JavaScript to be easy to write, and the helpful error messages help resolve the differences along the way.

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.