More working in F#.  I’m getting the hang of functional programming, though I still don’t want to spend my life coding in it.  Its definitely has some cool uses, but I’ll take my imperative model for most things!

We had to write Merge Sort in F#, which was fun.  This was a quick and dirty solution that I wrote pretty quick.  It works, but its slow.  I’m sure there is a faster way to do it, but its kind of pointless in my mind since you can write a faster imperative merge sort. Meh, whatever.

 

let rec splitter org_list new_list half counter =
    if(counter < half) then
        let head = List.head org_list
        splitter (List.tail org_list) (head :: new_list) half (counter + 1)
    else
        new_list,org_list

let split list =
    match list with
    | [] -> ([], [])
    | a::[] -> ([a], [])
    | a::b::[] -> ([a], [b])
    | _ ->
        splitter list [] (list.Length / 2) 0

let rec merge_helper list_left list_right list_final =
    match list_left with
    | [] -> list_final @ list_right
    | head::tail ->
        if(list_right.Length > 0)then
            if(head < list_right.Head)then
                let head_list = [head]
                merge_helper tail list_right (list_final @ head_list)
            else
                let head_list = [list_right.Head]
                merge_helper list_left (List.tail list_right) (list_final@head_list)
        else
            list_final @ list_left

let merge list_left list_right =
    merge_helper list_left list_right []

let rec merge_sort list =
    match list with
    | [] -> []
    | e::[] -> [e]
    |_ ->
        let (l,r) = split list
        let ll = merge_sort l
        let rr = merge_sort r
        merge ll rr

 

“In a room full of top software designers, if two agree on the same thing, that’s a majority.”
– Bill Curtis

Advertisement