Learning F# — Binary Search Tree

It’s no secret that I’m a big fan of functional programming languages. Being quite enamored with Ocaml I always wanted to get into F#, but its strong ties to the Windows ecosystem kept me from it for the longest time. However, this changed with the open-source release of .NET Core, so a bit less than a month ago I finally got serious about my F# learning.

I’m mainly using The Book of F# (Amazon affiliate link), the F# for fun and profit website and the official documentation as learning materials, but in order to truly learn a language one has to use it. So I enrolled in Exercism’s F# track and so far solved about 20 of the problems. I’ll pick some of the more interesting solutions and write about them in order to show off some of F#’s features.

Binary Search Trees

Binary Search Trees (BST) are data structures that keep their data in sorted order, allowing for lookup, insert and delete operations with an average time complexity of O(log n). This is done by conducting a binary search, where the tree is traversed from root to leaf, with smaller elements than the current node going into left subtree and bigger elements going into the right subtree:

F# Solution

To represent a tree in my solution, I chose to define a generic record type, which consists of optional left and right subtrees and a data attribute specifying the value of the current node:

type Node<'T> = {
    left: Node<'T> option;
    data: 'T;
    right: Node<'T> option
}

Exercism’s unit tests expect 3 functions for accessing a node’s elements, which trivially map unto the record’s attributes:

let left node = node.left

let right node = node.right

let data node = node.data

The create function is used to build up a BST from a list of items. The unit tests specified no behavior for an empty input array and since I did this exercise in TDD fashion I chose to ignore this case. While an empty search tree doesn’t make much sense in the first place, it’s not a particularly robust solution, so for production code I’d probably make the tree a discriminated union with Empty and Node<'T> constructors.

I implemented create using a local insert function, which uses pattern matching with guards to build up the tree. This function is applied to the input list with List.fold:

let create items =
    let rec insert x = function
    | None -> {left = None; data = x; right = None}
    | Some(t) when x <= t.data -> {t with left = Some(t.left |> insert x)}
    | Some(t) -> {t with right = Some(t.right |> insert x)}

    items
    |> List.fold (fun bst x -> Some(insert x bst)) None
    |> Option.get

The last requirement of the unit tests was extracting the data of the binary search tree as sorted list. This is done via the nested sort function, which recursively sorts a node’s left and right subtrees until it reaches the leaf nodes and concatenates the resulting lists:

let rec sortedData node =
   let rec sort = function
       | None -> []
       | Some(node) -> (sort node.left) @ [node.data] @ (sort node.right)
   node |> Some |> sort

Conclusion

F# proved itself to be very suitable for this task, since its expressive syntax, record types and pattern matching allowed for a concise and declarative solution to the problem.