Skip to main content

Trees: I can't be-leaf them

It's been a while since I've really dived into functional programming like I had when I was working on the parser project. In an attempt to better express myself functionally I'm going to run through the common algorithms/data structures in both C# and F# using each as intended.

A few posts back I posted an implementation of merge sort. Merge sort, in it's divide & conquer nature lends itself well to functional programming because after division a new container is returned with the sorted items much like how you would approach a problem in an immutable fashion. I'll come back to other sorting algorithms at another point, but I want to dive into trees.

Starting with a binary search tree and working through seemed like a sensible place to start. I wanted to start with the F# version and follow with the C# version.


1
2
3
4
 // A tree node.  
 type 'a BSTNode =   
     | Node of 'a * 'a BSTNode * 'a BSTNode  
     | Leaf  

So far so good, concise discriminated union to store our data and we can use any type to populate the value. The first obvious thing to do is insert values into the tree. After a bit of thought I came up with this:


1
2
3
4
5
6
 // Insert a new value into the tree.  
 let rec Insert value = function  
   | Leaf -> Node(value, Leaf, Leaf);  
   | Node(v, left, right) when value < v -> Node(v, Insert value left, right);  
   | Node(v, left, right) when value > v -> Node(v, left, Insert value right);  
   | Node(_, _, _) as node -> node  

Pattern match the node in a recursive function, if it's empty, make the empty node a new node with the value. If it's not empty, decompose the node, compare the value against the one we want to insert and run the insert function on the most appropriate node, and then handle the default case.

Finding a value in the tree is pretty much the same idea except that instead of creating a new node we just want to give back the one we found, so it doesn't take much of an adjustment to get something like this:


1
2
3
4
5
6
7
 // Find a specific value within the tree.   
 let rec Find value = function  
   | Leaf -> Leaf  
   | Node(v, left, right) as node when v = value -> node  
   | Node(v, left, right) when value > v -> Find value right  
   | Node(v, left, right) when value < v -> Find value left  
   | Node(_, _, _) -> Leaf  

It's very concise and it works just fine.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
 [<entrypoint>]  
 let main argv =   
   // Create a root node.  
   let root = Node(5, Leaf, Leaf);  
   // Add some more items.  
   let root = Insert 3 root;  
   let root = Insert 4 root;  
   let root = Insert 2 root;  
   let root = Insert 1 root;  
   // Find the four.  
   let four = Find 4 root;  
   0  


Of course, the C# implementation needs a different approach, as it's an object oriented language. It seems sensible to start with the same 3 important points, the value and the children. We're missing the type inference we get in F# but we do have generics.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
 public class BSTNode<t> where T  
 {  
   private T Value;  
   private BSTNode<t> Left;  
   private BSTNode<t> Right;  
   public BSTNode(T value)  
   {  
     Value = value;  
     Left = null;  
     Right = null;  
   }  
 }  

As before, insert seems like the sensible next thing to implement. However, there's a problem. You can't apply the standard operators to generic types but there's a bit of a workaround in adding a constraint to T to IComparable:


1
 public class BSTNode<t> where T : IComparable  

 and using CompareTo.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 /// <summary>  
 /// Add a value below the current node.  
 /// </summary>  
 /// <param name="value"></param>  
 public void Insert(T value)  
 {  
   if (value.CompareTo(Value) == 0)  
   {  
     return;  
   }  
   else if (value.CompareTo(Value) < 0)  
   {  
     if (Left == null)  
     {  
       Left = new BSTNode<T>(value);  
       return;  
     }  
     Left.Insert(value);  
   }  
   else  
   {  
     if (Right == null)  
     {  
       Right = new BSTNode<t>(value);  
       return;  
     }  
     Right.Insert(value);  
   }  
 }  

That's a lot more code than the F# implementation but they work in a similar way, something that it still has in common with Find:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 /// <summary>  
 /// Finds the Node with a given value, if it exists.  
 /// </summary>  
 /// <param name="value">The <see cref="int"/> value to find.</param>  
 /// <returns>The <see cref="BSTNode"/> containing the value, or null.</returns>  
 public BSTNode<t> Find(int value)  
 {  
   if (value.CompareTo(Value) == 0)  
   {  
     return this;  
   }  
   else if (value.CompareTo(Value) < 0)  
   {  
     if (Left != null)  
     {  
       return Left.Find(value);  
     }  
     return null;  
   }  
   else  
   {  
     if (Right != null)  
     {  
       return Right.Find(value);  
     }  
     return null;  
   }  
 }  

It's pretty clear to read and still works fine.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 class Program  
 {  
   static void Main(string[] args)  
   {  
     BSTNode<int> root = new BSTNode<int>(10);  
     root.Insert(5);  
     root.Insert(15);  
     root.Insert(7);  
     root.Insert(6);  
   }  
 }  



Continued in the next post with deletion of nodes.

Popular posts from this blog

Constructing a Trie in F#

This post might get a bit more context next week, but essentially, in continuation of looking at data structures in F# and C# I picked prefix trees (tries) as the next step. A trie is similar to a BST except the search is cumulative. A simple example would be building a spellchecker. The spell checker can use the structure to see if a word exists quickly and efficiently.

It works by creating a new node for each part of the word, using existing nodes if they're already in place. You can see in this diagram an example structure after an insertion of several words.

In the above diagram the words ANT, AND, BATS have been added into the data structure. You'll notice that the word BATS can also be the word BAT and that becomes a part of the structure, setting a value at each node to state if this is a place that a word terminates.

1 2 3 4// Node type for storing a trie. typeTrieNode=|Nodeofchar*TrieNodelist*bool|RootofTrieNodelist
I defined the type to have 2 options. The root node,…

A Docker Experiment

Containers are a topic that have been rising in occurrence for me, for the last year or so. From using them as part of the architecture at work or for various pet projects friends have been working on. I figured it was time to experiment myself and get to grips with what people have been talking about. It seemed like a good idea to find some introductory material that would give me an overview of its uses without delving too far into the details so I could see what it actually was, so I found a PluralSight course about Docker, specifically “Docker and Containers:The Big Picture”. This gave a nice overview of what Docker is, and more importantly what it was trying to achieve and how to use it. With a bit more of an understanding, I wanted to use it for something, preferably something familiar. I decided to try setting up ElasticSearch and Kibana containers, where Kibana would visualize the ElasticSearch data. I used bits of this article along the way as a guide, if you'd prefer a more…

Self-Producing an EP Pt.5: Mixing

After some discussion we opted to mix it ourselves for a few reasons.

It's our first EP, it's not going to be heard by a huge amount of people and while it's important that it sounds good, it's expensive to get done properly and we might be able to manage 'good enough' on our own with a lot of work.Mixing as an online service seems to be the main way to go for small/starting out bands and that seems too creatively detached. There are many stories floating around of people who've sent things off for mixing and the mixer has a much different idea of how it sounds.
Maybe it's not the best choice, but it seemed an acceptable risk that we would at least attempt to have it 'look' how we want and it be a bit wonky than potentially end up with something we're not happy with in a different way. The benefit would have been being able to just ship the stems off and make it someone else's problem instead of weeks of being unsure while swimming in the…