在OCaml中旋转列表

Question

我想编写一个函数rotate n l，它返回一个包含与l相同元素的新列表，向右旋转“n”。例如，

rotate 0 [1;2;3;4]应该返回[1;2;3;4] rotate 1 [1;2;3;4]应该返回[4;1;2;3] rotate 2 [1;2;3;4]应该返回[3;4;1;2] rotate 3 [1;2;3;4]应该返回[2;3;4;1] rotate 4 [1;2;3;4]应该返回[1;2;3;4] 等等

rotate n对于n的行为小于0应该与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

同意杰弗里，向我们展示你的尝试。这是一个小提示，以防您需要开始。如果你可以编写一个只执行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)

Answer 2

这个问题可以通过组合这三个函数来解决：

cat（skip（list，places），take（list，places））

实现如下：

let rec cat = function
    ([], y) -> y
    | (x::xs, y) -> x :: cat (xs, y)

let rec skip = function
    ([], _) -> []
    | (_::xs as xs1, c) -> if c > 0 then skip(xs, c - 1) else xs1

let rec take = function
    ([], _) -> []
    | (x::xs, c) -> if c > 0 then x :: take(xs, c - 1) else []

let cycle l i =
    cat (skip (l, i), take (l, i))

循环（[1; 2; 3; 4; 5; 6]，3）;;

val it：int list = [4; 5; 6; 1; 2; 3]