f# - 从列表中删除最后一个元素的最简单方法

Question

我正在编写一个将采用整数列表的函数，例如:

let x = [1..5]

并应返回如下所示的无序列表:

[1;5;2;4;3]

所以，它应该取第一个元素，然后是最后一个，然后是第二个元素，最后一个等等......

到目前为止，我已经编写了这个函数:

let rec reshuffle list: List<int> =
  match list with
  | [] -> []
  | head :: tail -> [head;list |> List.last] @reshuffle tail

我得到这个答案:

[1; 5; 2; 5; 3; 5; 4; 5; 5; 5]

似乎是因为每次递归执行该函数时，都没有删除最后一个元素。如何删除函数中的头部和尾部？

Answer 1

如果我们假设不允许使用任何库函数，并试图避免一次又一次地为“无”处理列表，我建议这样做。

我们首先反转初始列表，即只执行一次。
我们遍历这对列表并中途停止，从两个列表中累积当前项目。
起始累加器要么为空，要么包含“中间”项，具体取决于初始列表的长度是否为奇数/偶数。

为此，我们需要一个函数来反转列表:

let reverse xs =
  let rec aux acc = function
    | []      -> acc
    | x :: xs -> aux (x :: acc) xs
  aux [] xs

然后我们需要一个函数来获取列表的长度:

// not tail-rec
let rec length = function
  | []      -> 0
  | _ :: xs -> 1 + length xs

最后我们可以编写所需的函数:

let reshuffle xs =
  let reversed = reverse xs

  let rec aux acc = function
    | -1    -> acc
    | index -> let newAcc = xs.[index] :: reversed.[index] :: acc
               aux newAcc (index - 1)

  let theLength = length xs
  let startAcc = if theLength % 2 = 0
                 then []
                 else [ xs.[theLength / 2] ]

  aux startAcc (theLength / 2 - 1)

或者，如果您认为在某个索引上递归感觉像是某种“作弊”并且递归应该出现在列表中，您可以使用它:
(哪个更短但会做“双重”工作，一半“没有”)

let reshuffle xs =
  let rec aux acc = function
    | x :: xs, r :: rs -> aux (r :: x :: acc) (xs, rs)
    | _                -> acc

  let full = aux [] (xs, reverse xs)
  full.[.. length xs - 1]

我们构建了完整的“对”列表，因此我们从初始和对称中得到了一个双倍大小的列表。
从那以后，我们只首先返回“长度”。