recursion - F# 拆分函数

Question

我正在构建一个合并排序函数，而我的拆分方法给了我一个值限制错误。我正在使用 2 个累积参数，即拆分产生的 2 个列表，最后我将它们打包成一个元组以供返回。但是我遇到了一个值限制错误，我无法弄清楚问题是什么。有没有人有任何想法？

let split lst = 
    let a = []
    let b = []
    let ctr = 0
    let rec helper (lst,l1,l2,ctr) =
        match lst with
          | [] -> [] 
          | x::xs -> if ctr%2 = 0 then helper(xs, x::l1, l2, ctr+1)
                    else 
                    helper(xs, l1, x::l2, ctr+1)
    helper (lst, a, b, ctr)
    (a,b)

任何输入表示赞赏。

Answer 1

正如您编写的那样，该代码实际上没有任何意义。 F# 默认使用不可变值，因此您的函数，正如它当前编写的那样，可以简化为:

let split lst = 
    let a = []
    let b = []
    (a,b)

这可能不是你想要的。事实上，由于不可变的绑定(bind)，预先声明 a, b 没有任何值(value)。和 ctr .

这是一个可以解决问题的递归函数:

let split lst = 
    let rec helper lst l1 l2 ctr =
        match lst with
        | [] -> l1, l2 // return accumulated lists
        | x::xs -> 
            if ctr%2 = 0 then 
                helper xs (x::l1) l2 (ctr+1) // prepend x to list 1 and increment
            else 
                helper xs l1 (x::l2) (ctr+1) // prepend x to list 2 and increment
    helper lst [] [] 0

除了使用递归函数，您还可以使用 List.fold 来解决此问题。 , fold是一个高阶函数，它概括了我们在上面的递归函数中明确描述的累积过程。

这种方法更简洁一些，但对于函数式编程的新手来说很可能不太熟悉，所以我试图更详细地描述这个过程。

let split2 lst =
    /// Take a running total of each list and a index*value and return a new 
    /// pair of lists with the supplied value prepended to the correct list
    let splitFolder (l1, l2) (i, x) =
        match i % 2 = 0 with
        |true -> x :: l1, l2 // return list 1 with x prepended and list2
        |false -> l1, x :: l2 // return list 1 and list 2 with x prepended
    lst
    |> List.mapi (fun i x -> i, x) // map list of values to list of index*values
    |> List.fold (splitFolder) ([],[]) // fold over the list using the splitFolder function