Skip to main content

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.  
 let rec MergeSort (input: int list) =   
   // Merges 2 lists together in ascended sorted order.  
   let Merge (left: int list, right: int list) =  
     let rec mergeLists (left: int list, right: int list, output: int list) =  
       match (left, right, output) with  
         | ([], right, output) -> output@right  
         | (left, [], output) -> output@left  
         | (left, right, output) when left.Head < right.Head -> mergeLists (left.Tail, right, output@[left.Head])  
         | (left, right, output) ->mergeLists (left, right.Tail, output@[right.Head])  
     mergeLists (left, right, [])  
   // Process the input.  
   if input.Length = 0 then []  
   else if input.Length = 1 then input  
   else if input.Length = 2 then  
     if input.[0] > input.[1] then [input.[1]; input.[0]]  
     else input  
   else  
     // Valid list size found, sort and merge.  
     let left = MergeSort (input |> Seq.take (input.Length / 2) |> Seq.toList)  
     let right = MergeSort (input |> Seq.skip (input.Length / 2) |> Seq.toList)  
     Merge (left, right)  

It could be more compact perhaps but given that I don't think there's a performance issue I like it in the slightly more readable format.

Comments

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…