Skip to main content

Posts

Showing posts from April, 2015

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,…

The Harper Lee Experiment

Harper Lee, author of 'To Kill a Mockingbird' wrote the book after a friend gifted her 1 years salary to write whatever she wanted. No-one would argue that that time or money was misspent. It made me think however, when I randomly remembered it earlier in the day about how with some changed variables it could apply to a developer. Then it became a bit of a thought experiment.

Let's say you're random developer with some experience. Not necessarily lots, but enough to be comfortable. On new years eve, a friend (whose reasoning skills you'd likely and understandably question at this point) offers you 1 years salary to create whatever you like under the understanding that after December 31st that this creation would be your livelihood. Through some sort of magic your day job is a thing of the past and you are free to do as you please.

We'll also say as a matter of co-incidence you happen to have been sitting on an idea for some software that a blue box inhabiting m…

Trees: I still can't be-leaf them

Carrying on from the last post, I wanted to add deletion to the BST. My first attempt at this was in F#. I decided the best way to do it was to find the node that contained the value and if it only had one child node, replace it with that otherwise add the tree from the right to the tree from the left. The impact of this decision will be that the height of the tree is increased by an unknown amount and will affect performance, but binary search trees are unbalanced anyway and it's just for fun. All of the cases were simple up until the point where the right tree might need to be added to the left.


1 2 3 4 5 6 7 8// Remove a given value fron the tree.letrecRemovevalue=function|Leaf->Leaf|Node(v, left, right)whenvalue<> v ->Node(v,Removevalue left,Removevalue right)|Node(v, left,Leaf)-> left |Node(v,Leaf, right)-> right |Node(v,Leaf,Leaf)->Leaf|Node(_,_,_)as node -> node

For that, I'd need a new function that would do the same as insertion but…

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=|Nodeof'a *'a BSTNode*'a BSTNode|Leaf
So far so good, concise discriminated union to store our dat…

F# Poker Hand Analysis and GitHub

The F# Poker Hand Analysis code I'd written about in previous posts is now public on GitHub. I tidied it up slightly and put it up so that A) I don't lose it, because I thought it was interesting work and B) So that perhaps I can come back to it now and again, which is much easier when it's not lurking on a USB stick at the bottom of my bag. It's functionality includes:
- Reads in files containing hand histories and parses them form the perspective of the user.
- The information stored is complete, detailing every action made by each player.
- Unit tested extensively using existing and real hand history files.
- Can calculate a players 'VPIP' (voluntarily put in pot, % of times the player willingly engages in action) over a provided data set.

It's implemented with F#'s native functional features and as such lends itself well to concurrency. I'm hoping to continue by calculating players hand ranges, but if not I have some ideas about similar work in …

Functional Programming and Algorithms

I found an old post I made sitting in my Gists on Github where I'd implemented merge sort in F#. At the time I was quite interested in the way algorithms change when you're 'confined' to a stateless world. For some it's easier than others and I might do some experimentation with them at some point. I do have a book on it that I'd planned to read at some point in the depths of my Kindle. Here was the code I found anyway:


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 // Learn more about F# at http://fsharp.net // Performs Merge Sort on a list of strings. letrecMergeSort(input:intlist)=// Merges 2 lists together in ascended sorted order. letMerge(left:intlist, right:intlist)=letrec mergeLists (left:intlist, right:intlist, output:intlist)=match(left, right, output)with|([], right, output)-> output@right |(left,[], output)-> output@left |(left, right, output)when left.Head< right.Head-> mergeLists (left.Ta…

My Slippery Mind

I completely forgot that this existed. I only noticed when the domain came up for renewal and I thought "I should put a blog there" and realised I already had, and even posted to it. Weird. It's been a pretty busy 2 years since the previous post. My team in Microsoft, Mediaroom moved over to our new home in Ericsson and continued working on and announcing the project that had been keeping us busy all that time. I'll be back.