不明白这段代码

Question

我是 F# 新手，发现了一些我想使用的代码。此代码接受一个列表并返回列表的后半部分。我希望有人能够逐行介绍它的作用。我想更改它，以便它返回列表的前半部分。这是我的问题之后的代码。

let cut l = 
   let rec cut = function
       | xs, ([] | [_]) -> xs  
       | [], _ -> []
       | x::xs, y::y'::ys -> cut (xs, ys)
   cut (l, l)

= function 的作用是什么？

我很确定 | xs，([] | [_]) -> xs 是如果有 xs 将其添加到列表中

我不明白这是做什么的 | []，_-> []

| x::xs, y::y'::ys -> cut (xs, ys)：我理解前半部分，它创建了两个子列表，让我困惑的是为什么 cut 发送尾部 xs 和 ys 。 cut 不是只接受一个参数吗？

Answer 1

该函数返回给定列表的后半部分。

代码中有趣的部分只是嵌套（递归）函数，因为外部函数的唯一目的是调用嵌套函数并向其传递指定列表两次。嵌套的 cut 函数有两个参数（作为元组），因此它的类型是：

cut : 'a list * 'a list -> 'a list

当递归调用自身时，这是被调用的函数（这解释了为什么使用两个参数调用它）。以下是注释代码：

// The 'function' syntax means that the arguments of the function are matched against 
// several clauses. When the arguments (lists) match the clause, the clause is selected
// and its body will be executed. 
let rec cut = function
  // When the second list is empty or contains a single element,
  // the function return all elements of the first list
  | xs, ([] | [_]) -> xs  
  // When the first list is empty, return empty list
  | [], _ -> []
  // When first list is non-empty and second contains at least two elements,
  // the function takes one element from the first list and two elements from 
  // the second list (x, y, y'), ignores them and calls itself with the 
  // remaining lists as arguments.
  | x::xs, y::y'::ys -> cut (xs, ys)

cut ([ 1 .. 10 ], [ 1 .. 10 ])

该函数的思想是迭代同一列表的两个副本。在每个递归步骤中，它都会从第二个元素中跳过两个元素，并从第一个元素中跳过一个元素。当它到达第二个列表的末尾时，第一个列表包含列表的后半部分（因为该函数跳过其元素的速度慢了两倍）。

要获取列表的前半部分，您需要向内部递归 cut 函数添加其他参数。您可以使用它来累积第一个列表中的元素。同样，您需要以两倍的速度跳过列表之一的元素。您不需要跳过另一个列表的第一个元素，而是需要将它们添加到累加器中。

我不会给你一个完整的解决方案，但为了给你一些想法，这里是伪代码：

  | x::xs, _::_::ys -> 
      // Call 'cut' recursively to process 'xs' and 'ys'
      // and add the element 'x' to the accumulator.

编写函数的另一种方法是使用match而不是< code>function 并将两个参数编写为标准多个参数（而不是使用元组）。当忽略最后一个子句中的元素时，也可以使用 _ 因为不需要它们的名称：

let rec cut l1 l2 = 
  match l1, l2 with
  | xs, ([] | [_]) -> xs  
  | [], _ -> []
  | _::xs, _::_::ys -> cut xs ys

cut [ 1 .. 10 ] [ 1 .. 10 ]

Answer 2

将其更改为返回列表的前半部分的最简单方法是：将反转的列表传递到内部函数并反转结果。

let cut l = 
  let rec cut = function
    | xs, ([] | [_]) -> xs  
    | [], _ -> []
    | x::xs, y::y'::ys -> cut (xs, ys)
  let k = List.rev l
  cut (k, k) |> List.rev

没有列表.rev

let cut l = 
  let rec cut f = function
    | x::_, [_] -> f [x]
    | _, [] -> f []
    | [], _ -> []
    | x::xs, _::_::ys -> cut (fun acc -> f (x::acc)) (xs, ys)
  cut id (l, l)

Answer 3

查看 cut 函数正在执行的操作的最简单方法是认识到下面的行

| x::xs, y::y'::ys -> cut (xs, ys)

清空第二个列表的速度是第一个列表的两倍。这是因为它从 ys 列表的头部拉出 2 个元素，从 xs 列表的头部拉出 1 个元素，并将它们丢弃。如果它连续这样做，那么 ys 将首先终止，当它终止时，xs 将包含原始列表的下半部分。