0

试图编写一个递归函数，将列表削减 n。然后返回 2 个列表。所以如果我通过

cut(2, [5;10;4;2;7]);;
  val it : int list * int list = ([5; 10], [4; 2; 7])

我想得到类似的东西。

let rec cut (n, xs) = 
        match n, xs with 
        | 0, xt -> (n, xs)
        | n, x::xt -> cut(n, xt), xs;;

请帮忙。

4

2 回答 2

2

我将解释@MisterMetaphors 递归函数。

cut 函数不是递归的，但 aux 是递归的，它通过从 n 倒数并从传递给 cut 的列表的头部删除元素来工作。

假设你这样调用 cut cut 2 [ 3; 4; 5; 7; 8 ]。aux 是一个模式匹配函数，采用三个参数：n、分区 1、分区 2。分区 1 开始时是一个空列表，分区 2 开始时是传递给 cut 的完整列表。

第一次 aux 将匹配第二个子句，然后它会用参数 (1, [3], [4; 5; 7; 8]) 调用自己。下次它还会匹配第二个子句，现在它用 (0, [4; 3], [5; 7; 8]) 调用自己。第三次也是最后一次匹配第一个子句（n=0），它将返回一个包含 xs 和 ys 的元组。

但是请注意，xs 的元素顺序相反，因为每个元素都是预先添加的（使用 cons 运算符 ::）。这样做的原因是因为它是一个 O(1) 操作，而左侧的附加运算符 @ 是 O(n)。

由于 xs 是逆序的，因此函数中的最后一个表达式是 xs 的逆序。

另一种略短的定义可能是：

let cut n xs =
    let rec aux = function
        | 0, xs, ys -> List.rev xs, ys
        | n, xs, y :: ys -> aux (n - 1, y :: xs, ys)
        | _ -> failwith "invalid arguments"
    aux (n, [], xs)
于 2013-05-23T08:43:30.587 回答
1

最好在列表或序列上结合内置函数来实现这一点：

let cut' (n, xs) =
    Seq.take n xs, Seq.skip n xs

递归地，您的函数可以这样定义：

let cut (n, xs) =
    let rec aux = function
        | 0, xs, ys -> xs, ys
        | n, xs, y :: ys -> aux (n - 1, y :: xs, ys)
        | _ -> failwith "invalid arguments"
    let l, r = aux (n, [], xs)
    (List.rev l, r)
于 2013-05-23T06:34:11.000 回答