Friday, 17 April 2015

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.