list - 在 OCaml 中旋转列表

Question

我想写一个函数 rotate n l 返回一个包含与 l 相同的元素的新列表，“旋转” n 次到正确的。例如，

rotate 0 [1;2;3;4] should return [1;2;3;4]
rotate 1 [1;2;3;4] should return [4;1;2;3]
rotate 2 [1;2;3;4] should return [3;4;1;2]
rotate 3 [1;2;3;4] should return [2;3;4;1]
rotate 4 [1;2;3;4] should return [1;2;3;4]
etc.

当 n 小于 0 时，rotate n 的行为应该与 n 等于 0 时相同。我想在不使用 Pervasives 的列表连接运算符 @ 的情况下编写它。

更新:这是我写的旋转函数:

let rot1 l =
  let rec iterate acc = function
      [] -> []
    | [x] -> x :: List.rev acc
    | x :: l -> iterate (x :: acc) l
  in
  iterate [] l;;

但我希望它在不使用 List.rev 的情况下做同样的事情。有办法做到这一点吗？

Answer 1

同意 Jeffrey 的观点，向我们展示您的尝试。如果您需要开始，这里有一个小提示。如果您可以编写一个仅执行 1 次旋转的函数，即相当于 rotate 1 l。 (我称之为 one_rot)。那么rotate可以很容易的定义为:

let rec rotate n l = 
  match n with 
  | 0 -> l
  | _ -> rotate (n-1) (one_rot l)

您的解决方案非常适合我。不确定您对 List.rev 有什么看法，但这里有一个完全独立的 one_rot。请注意，我们必须牺牲尾递归。您也可以将其缩短很多:

let rec last = function
  | [] -> assert false 
  | [x] -> x
  | x::xs -> last xs

let rec init = function
  | [] -> []
  | [x] -> []
  | x::xs -> x::(init xs)

let one_rot l = (last l)::(init l)