Hands-On with Gleam: Building and Improving a Binary Search Tree

Gleam is a functional programming language that proudly aims to be simple. This means you have a few straightforward tools to solve problems. That's why it's such a great language for zoning out from other perspectives and allowing you to solve coding problems differently than you are used to.

Let's zone out. Build a binary search tree and see how we can improve the code step by step, and what we can learn from it.

Binary search trees perform better than arrays when inserting or retrieving sortable data. They are built from nodes, with each node containing data and two pointers to other nodes. The left node has a value smaller than or equal to the value stored in the current node, while the right node stores a value larger than that stored in the current node.

In Gleam you can write a type to represent this:

pub type Tree {
  Node(data: Int, left: Tree, right: Tree)
  Nil
}

In Gleam, we can use pattern matching and the 'case' expression to add new data to the tree. My first attempt at writing a function to add a new node to a tree was as follows:

fn add_to_tree(tree: Tree, data: Int) -> Tree {
  case tree {
    Node(tree_data, Nil, right) if data <= tree_data -> {
      Node(tree_data, Node(data, Nil, Nil), right)
    }
    Node(tree_data, left, Nil) if data > tree_data -> {
      Node(tree_data, left, Node(data, Nil, Nil))
    }
    Node(tree_data, left, right) if data <= tree_data -> {
      Node(tree_data, add_to_tree(left, data), right)
    }
    Node(tree_data, left, right) if data > tree_data -> {
      Node(tree_data, left, add_to_tree(right, data))
    }
    Nil -> Node(data, Nil, Nil)
    _ -> panic as "Invalid tree"
  }
}

A few things might bother you with this code. Primarily, the last branch shouldn't be needed. However, since Gleam doesn't try to evaluate any complex pattern with 'if', the code won't compile without that last branch, even though we know it is impossible for the data to take that route.

Nest a little bit.

Nest a little bit.
Coming from JavaScript, where "nevernesting" is a principle, it might feel unnatural, but in Gleam, we can sometimes nest and benefit from it. First, let's move the comparison one nested level down.

I've included a picture from my editor of this refactor to illustrate how easy and nice it is, thanks to the Gleam language server.

Let's delete those lines marked unreachable.

fn add_to_tree(tree: Tree, data: Int) -> Tree {
  case tree {
    Node(tree_data, left, right) -> {
      case data <= tree_data {
        True -> Node(tree_data, add_to_tree(left, data), right)
        False -> Node(tree_data, left, add_to_tree(right, data))
      }
    }
    Nil -> Node(data, Nil, Nil)
  }
}

Much better. Notice how we moved the real work inserting the data to the Nil case, it means our recursive function now only has one base case and one for deciding the direction in the tree. The last optimization can be to put the base case in the first position, but I will let you do that.

In summary, by leveraging Gleam's simplicity and powerful pattern matching, we streamlined our binary search tree implementation. We reduced complexity and made the code more intuitive, enhancing readability and maintainability. With each step, we learned to harness Gleam's features to write cleaner, more efficient code. Happy coding!