3

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

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]
等等。

小于 0 的行为应该与等于 0 的行为相同。rotate n我想在不使用.nn@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. 有没有办法做到这一点？

4

2 回答 2

3

同意杰弗里，向我们展示你的尝试。如果您需要开始，这里有一个小提示。如果您可以编写一个仅执行 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)
于 2013-03-26T01:25:47.850 回答
0

This problem can be solved by combining these 3 functions:

cat(skip(list, places), take(list, places))

The implementation looks like:

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))

cycle ([1;2;3;4;5;6], 3);;

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

于 2018-07-03T02:45:31.820 回答