## DEV Community is a community of 862,249 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Michael Kohl

Posted on • Updated on • Originally published at citizen428.net

# Learning F# — Binary Search Tree

Originally published on my blog.

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#, 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.

## Discussion (2)

Michael Kohl • Edited on

I agree. As much as I like Haskell in general, I take pragmatism over purity any day of the week. F# occupies a nice space as modern Ocaml on top of .NET, similar to what Clojure did for Lisp and the JVM.

F# really is a pleasure to write and considering how recently I picked it up I’m constantly surprised by how productive I feel when writing it.