Recursion and Data Structures in Unison
A look at how to solve programming problems through recursion
When your programming language does not support loops, you need to use recursion or higher-order functions. In my previous article I covered higher-order functions such as map
, filter
and fold
in the Unison programming language. In this story, I want to focus more on recursion in general and how it can be used effectively to search data structures such as binary trees.
Factorial and Summation
The factorial of n
is n * (n-1) * (n-2) * ... * 3 * 2 * 1
. That means, you can find the factorial of n
by multiplying with the factorial of n - 1
. It is an operation that naturally leads to a recursive definition:
fac : Nat -> Nat
fac n = if n <= 1
then 1
else n * (fac (n - 1))
Summation is a bit trickier, as we need to traverse a list of numbers and handle cases where the list is empty. Pattern matching is a good way of handling that in Unison. In Unison, you can prepend an element x
to a list xs
using the +:
operator. Thus, 4 +: [3, 2]
is equal to [4, 3, 2]
. It is also possible to append using the :+
operator. Thus, [3, 2] :+ 1
results in [3, 2, 1]
. We can use these operators in pattern matching to extract different parts of a list. The expression y +: ys
will extract the first element a list into the y
variable and the remainder of the list into ys
.
The list might be empty, which means it will not be possible to match the pattern. That is why we need to provide the empty list []
as a possible pattern to match first.
sum : [Nat] -> Nat
sum xs = match xs with
[] -> 0
y +: ys -> y + sum ys
The Fibonacci Sequence of Numbers
It is a cliché how often the fibonacci sequence pops up in programming examples. You may ask why so many loves to use it as an example. It is because it is somewhat useful. It explains how many things grow. Furthermore, it was originally used to model the growth of rabbits. The idea is that the number of new rabbits is always related to the number of rabbits born some time ago, since rabbits need to get old enough before they have offspring. The same logic applies to all sorts of population growth.
If you want a great introduction and animated explanation of Fibonacci numbers, I recommend the Mathigon website.
The fibonacci function is also relatively simple to implement and demonstrate recursion and control flow.
fib : Nat -> Nat
fib n = if (0 <= n) && (n <= 1)
then n
else (fib (n-1)) + (fib (n-2))
I actually use the Fibonacci function as a way to explain if-statement in the Julia programming language in my book Julia as a Second Language.
Searching Binary Trees
A classic recursive data structure is binary trees. Each tree node can have two child nodes, and each of these child nodes can have two child nodes as well. In the following code example, I am defining a parameterized type TreeNode
with two type parameters k
and v
which represent the types of the key and value stored on each tree node. If the type parameters had been titlecased, then they would have referred to actual concrete types. In this case, they can be anything.
unique type TreeNode k v =
ParentNode k v (TreeNode k v)
(TreeNode k v)
| LeafNode k v
| Empty
The definition above may look really odd to people not used to Haskell-like languages. For those of us more used to mainstream languages, it is what we would call a tagged union or enumeration.
It may help if I show what this would look like in Swift, as Swift use a more C-like syntax that more people are familiar with. Here is a simple Swift enumeration without any stored values:
// Swift enumeration
enum CompassPoint {
case north
case south
case east
case west
}
But we can make enumerations with stored values, so called tagged unions or sum types. The official Swift documentation uses a barcode example:
// Swift enumerations with stored values
enum Barcode {
case upc(Int, Int, Int, Int)
case qrCode(String)
}
But we can try to do the TreeNode
example in Swift instead:
// Swift enumeration faking our Unison binary tree nodes
enum TreeNode {
case ParentNode(Int, String, TreeNode, TreeNode)
case LeafNode(Int, String)
case Empty
}
Keep in mind this is not entirely the same as the Unison code as we have not parameterized the TreeNode
type. Instead, we have just hardcoded the key and values to be Int
and String
respectively. Anyway, let's look at how we can construct a tree of nodes in Unison:
node = (ParentNode 3 "three"
(LeafNode 2 "two")
(ParentNode 12 "twelve"
(LeafNode 8 "eight")
(LeafNode 42 "forty-two")))
Creating nodes is a lot like calling constructors in an object-oriented language. ParentNode
and LeafNode
are both of type TreeNode
, but they store different kinds of data. Keep in mind, there is no such thing as classes and inheritance in Unison. This is the way to build data structures in Unison.
Okay, so we got some data, but we want to be able to do stuff with it, such as searching through it for a value stored at a particular key. A binary search tree is usually organized so that the left child node has keys with lower value than the parent, while the right child node has keys with higher value than the parent node.
That organization allows us to search through the tree in O(log N)
time (big O notation). I wrote a function to do that called find
. At first, I made it entirely generic, but Unison refused to play along. Specifically, Unison didn't like that I made comparisons such as key <= k
in the code. The reason is that most operators are not generic. Every type has a different comparison operator. k <= key
in this code is actually short for k base.Nat.<= key
(I will explain this later).
Unison uses pattern matching to handle all the different variants of TreeNode
. That is pretty standard for most functional languages. Swift does it very similar except it calls it switch
instead of match
since that is what C-style developers are used to.
find : Nat -> TreeNode Nat v -> Optional v
find key node =
match node with
Empty -> None
LeafNode k v ->
if (k == key)
then Some v
else None
ParentNode k v left right ->
if k == key
then Some v
else if key <= k
then find key left
else find key right
If the node
value is a LeafNode
, then it will match the LeafNode k v
pattern and bind the key and value to the k
and v
identifiers. Notice that the return type of find
is not v
because you may not actually find anything on the supplied key. Optional
is a tagged union type, which can be either Some x
or None
. You will find the concept of Optional
in Rust, Haskell, Swift, Kotlin, and many other mainstream languages today.
Here is the find
function in action. It searches the tree node called node
which I defined earlier to find the value stored on the key 8.
> find 8 node
⧩
Some "eight"
To understand how we can make this binary tree more generic, we need to first understand how Unison picks functions to call. Remember that operators such as ==
and <=
and just function calls on infix form. 3 <= 4
is the same as (<=) 3 4
.
How Unison Picks a Function to Call
In an object-oriented language, a concrete method to call is decided at runtime by a lookup in the associated class or by using a virtual method table (vtable). I normally use Julia, where you register methods on functions. So if you have a <=
function, you can add a method for each type of object you want to compare. At runtime, Julia will pick the right method to call by looking at the types of all the arguments.
Unison cannot work like that because it is a statically typed language. You don't make type-based decisions at runtime. There isn't actually a <=
function in Unison. Instead, there is a base.Nat.<=
, base.Int.<=
and base.Float.<=
function. Actually, there are many more. You got the same with map
. There is a base.data.List.map
, base.data.Array.map
and base.data.Set.map
function.
Keep reading with a 7-day free trial
Subscribe to Erik Explores to keep reading this post and get 7 days of free access to the full post archives.