3

这就是我使用命令式风格在 F# 中实现合并排序的方式：

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

如果可能的话，您能否将其转换为替代的“功能”样式的实现并解释它是如何工作的？尽管我目前正在研究列表推导和所有这些，但我无法想出在这里使用它的想法。

4

2 回答 2

4

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')
于 2012-09-09T15:28:46.730 回答
1

要为 pad 添加一个更简单但幼稚的替代方案：

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

与 pad 类似，我们在函数参数上进行模式匹配。

  • 我首先将它们放入一个元组中，以便我可以同时对它们进行模式匹配。
  • 然后，我处理两个或两个参数都为空的基本情况。
  • 然后我使用when警卫检查哪个第一个项目更小
  • 最后，我将第一项作为另一个调用的结果，并将其merge与其余项中的较小项以及整个其他列表一起调用。因此，如果 的第一项x较小，我将x(fx在这种情况下) 的第一项附加到调用的结果中，以传入( )merge的其余部分和整个（因为 的第一项更大）。xxsyy
于 2012-09-11T19:07:21.680 回答