# Learning F# — Binary Search Tree

##### - fsharp exercism

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.

Comments powered by Talkyard.