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.