f# - 看不懂这段代码

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 而不是 function 并将两个参数写为标准的多参数(而不是使用元组)。当忽略最后一个子句中的元素时，也可以使用 _ 因为不需要它们的名称:

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

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