rewriting a code using pattern matching F#

Question

Hi Im very new to F# as well as programming. Im trying to learn it now and have enrolled to a course but i still dont seem to get it. pls help. Im trying to rewrite the following code:

let rec msort xs =
    let sz = List.length xs
    if sz < 2 then xs  
    else let n = sz / 2
        let ys = xs. [0..n-1]
        let zs = xs.[n..sz-1]
        in merge (msort ys) (msort zs)

//************ Utility-funktion merge

let rec merge xs ys =   if List.isEmpty xs then ys   else if
List.isEmpty ys then xs   else let x = List.head xs
        let y = List.head ys
        let xs = List.tail xs
        let ys = List.tail ys
        in if x < y then x :: merge xs (y::ys)
                else y :: merge (x::xs) ys  </i>

My solution - which isnt working:

let rec msort xs =
  let sz = List.length xs
    match sz with
    | sz < 2 -> xs
    |_ -> n = sz/2
          let ys = xs. [0..n-1]
          let zs = xs.[n..sz-1]
          in merge (msort ys) (msort zs)    


//************ Utility-funktinen merge

let rec merge xs ys =   match xs with   |[] -> [ys]
    match ys with
      |[] -> [xs]   |_ ->
        let x = List.head xs
        let y = List.head ys
        let xs = List.tail xs
        let ys = List.tail ys if x < y then x :: merge xs (y::ys)
                                  |_ ->
                                        y :: merge (x::xs) y

Answer 1

Notice that you can match over two values by writing them in a tuple and instead of let-binding list head and tail you can use pattern matching on the 'shape' of the list directly in the guards although the fact that the same name it's used for the whole list and later for the tail is a bit unfortunate as it can lead to confusion, but it works fine because F# shadows the values:

let rec merge xs ys = 
    match (xs, ys) with 
    | [], _ -> ys
    | _, [] -> xs
    | x::xs, y::ys -> 
        if x < y then x :: merge xs (y::ys)
        else y :: merge (x::xs) ys

let rec msort xs = 
    let sz = List.length xs 
    match sz with 
    | sz when sz < 2 -> xs 
    |_ -> 
        let n = sz/2 
        let ys = xs. [0..n-1] 
        let zs = xs.[n..sz-1]
        merge (msort ys) (msort zs)

You were missing the keyword when in the conditions of the guards. I also fixed some minor details in your original code.