CODEWITHSUNDEEP
f#mergesort
badmaash
badmaash

Reputation: 4845

How can I convert this imperative style merge-sort implementation into functional style?

This is how I implemented merge-sort in F# using imperative style:

let merge (l1: List<string>,  l2: List<string>) = 
 let r: List<string> = new List<string>()
 let mutable (i,j, cnt1, cnt2) =  (0,0, l1.Count, l2.Count)
 while i < cnt1 && j < cnt2 do
    if l1.[i] <= l2.[j] then
        r.Add (l1.[i])
        i <- i + 1
    else
        r.Add (l2.[j])
        j <- j + 1

 if i = cnt1 then
    while j < cnt2 do
        r.Add (l2.[j])
        j <- j + 1
 else    
    while i < cnt1 do
        r.Add (l1.[i])
        i <- i + 1
 r

Can you convert this to alternate 'functional' styled implementation and explain how it works, if possible? Even though I am studying list comprehensions and all that at the moment, I can't come up with an idea to use it here.

Upvotes: 3

Views: 401

Answers (2)

pad
pad

Reputation: 41290

You're using .NET List<'T> which is renamed to ResizeArray<'T> in F# to avoid confusion. If you use functional list, merge function would look like this:

let merge(xs, ys) =
    let rec loop xs ys acc =
        match xs, ys with
        | [], [] -> List.rev acc (* 1 *)
        | [], y::ys' -> loop xs ys' (y::acc) (* 2 *)
        | x::xs', [] -> loop xs' ys (x::acc) (* 3 *)
        | x::xs', y::_ when x <= y -> loop xs' ys (x::acc) (* 4 *)
        | _::_, y::ys' -> loop xs ys' (y::acc) (* 5 *)
    loop xs ys []

To explain this function in terms of your imperative version:

  • The 4th and 5th patterns are corresponding to the first while loop where you compare two current elements and add the smaller one into a resulting list.
  • The 2nd and 3rd patterns are similar to your 2nd and 3rd while loops.
  • The first pattern is the case where i = cnt1 and j = cnt2 and we should return results. Since a new element is always prepended to the accumulator, we need to reverse it to get a list in the increasing order.

To be precise, your merge function is just one part of merge-sort algorithm. You need a function to split a list in two halves, call merge-sort on two halves and merge two sorted halves into one. The split function below is left for you as an exercise.

let rec mergeSort ls =
    match ls with
    | [] | [_] -> ls
    | _  -> let xs, ys = split ls
            let xs', ys' = mergeSort xs, mergeSort ys
            merge(xs', ys')

Upvotes: 4

Geoff
Geoff

Reputation: 1634

To add a more simple but naive alternative to pad's:

let rec merge x y = 
    match (x, y) with
    | ([], []) -> []
    | ([], rest) -> rest
    | (rest, []) -> rest
    | (fx :: xs, fy :: _) when fx <= fy -> fx :: merge xs y
    | (fx :: _, fy :: ys) -> fy :: merge x ys

Similarly to pad's, we're pattern matching over the function parameters.

  • I first put them into a tuple so that I can pattern match them both at the same time.
  • I then take care of the base cases with both or either of the parameters being empty.
  • I then use when guard to check which first item is smaller
  • I finally take the first item and cons it to the result of another call to merge with the rest of the items the smaller item was taken from and the whole of the other list. So if the first item of x is smaller, I append the first item of x (fx in this case) to the result of a call to merge passing in the rest of x (xs) and the whole of y (because the first item of y was larger).

Upvotes: 1

Related Questions