2013-03-26 95 views
3

我想寫一個函數rotate n l,它返回一個新列表,其中包含與l相同的元素,「旋轉」n倍到右側。例如,OCaml中的旋轉列表

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。 有沒有辦法做到這一點?

+0

這看起來非常像功課。除非你展示一些你已經嘗試過的代碼,並描述如何以及爲什麼它不起作用,否則只有給你答案很難。 – 2013-03-26 01:17:30

回答

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

讓ROT1升= 讓REC迭代ACC =函數 [] - > [] | [x] - > x :: List.rev acc | x :: l - > iterate(x :: acc)l in iterate [] l ;; – 2013-03-26 02:30:13

+0

感謝您的提示。如果我可以使用列表函數,我知道如何編寫這些東西。但我不知道如何在沒有它的情況下編寫它。所以我寫了one_rot l函數,它可以工作,但我使用List.rev函數。有沒有辦法寫沒有List.rev? – 2013-03-26 02:32:44

+0

無視這個......... – rgrinberg 2013-03-26 05:49:40