Monday, 13 April 2015

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.