OCaml的 - 返回一個包含該列表

Question

的尾巴名單對於[1;2;3;4;5]，我想回到[[1;2;3;4;5];[2;3;4;5];[3;4;5;];[4;5];[5];[]]

我試圖使用列表庫，但我不能確定如何。到目前爲止，我知道我必須使用List.tl獲取列表而不第一個元素

let rec tailsoflist (l : 'a list) : 'a list list = 
    match l with 
     [] -> [[]] 
    | x::xs -> l::(tails xs) 

我這樣做遞歸，但現在我只想使用列表庫，而無需使用遞歸。

let tails (l : 'a list) : 'a list list 

編輯：對不起，我指定的函數返回的是不正確的。剛剛更新了正確的輸出。

Answer 1

正如我在評論說，這些都是l不是尾部而是l尾部的副本：

# let tails l = List.fold_right (fun e acc -> (e::(List.hd acc))::acc) l [[]] ;; 
val tails : 'a list -> 'a list list = <fun> 
# tails [1; 2; 3; 4] ;;- : int list list = [[1; 2; 3; 4]; [2; 3; 4]; [3; 4]; [4]; []] 

Answer 2

有編寫功能的內置功能方面沒有什麼好辦法。

你在你的問題給出的答案是好的，但它會更地道不註釋類型和使用function：

let rec tails = function 
    | [] -> [[]] 
    | _::xs' as xs -> xs::tails xs' 

其他語言，如F＃，提供一個List.unfold功能tails可以寫成就......而言。

Answer 3

「不使用遞歸」...爲什麼？遞歸是一個有用的工具，即使在List庫之外。

let rec suffixes = function 
| [] -> [[]] 
| hd::tl as suff -> suff :: suffixes tl 

你的函數（不編譯因爲你用tails代替tailsoflist）返回一個列表的後綴列表。由於列表結構，它比計算前綴更容易計算。

您可以從後綴表示前綴：

let prefixes li = List.map List.rev (suffixes (List.rev li));; 

你可以使用蓄電池直接做版本：

let prefixes li = 
    let rec pref acc = function 
    | [] -> List.rev acc :: [] 
    | hd::tl -> List.rev acc :: pref (hd :: acc) tl 
    in pref [] li 

，並使用List.fold_left，如果你想避免遞歸表達，但這是令人費解的，所以你應該更喜歡直接版本在我看來：

let prefixes li = 
    let acc, res = 
    List.fold_left 
     (fun (acc, res) e -> (e :: acc), (List.rev acc :: res)) 
     ([], []) li in 
    List.rev acc :: res 

最後，使用continuations可以破壞你的大腦，但我不記得確切的代碼。粗略地說，延續相當於直接版本的「累加器」。

Answer 4

啊，原來的詭計就是在原始列表上堆積鑄造tails作爲變形。這是在不使用List模塊上只是功能明確的遞歸方法來實現：

let tails l = List.rev ([] :: snd (List.fold_right 
    (fun _ (t,ts) -> List.tl t, t::ts) l (l, []))) 

它產生的尾巴像您期望：

# tails [1;2;3;4;5];; 
- : int list list = [[1; 2; 3; 4; 5]; [2; 3; 4; 5]; [3; 4; 5]; [4; 5]; [5]; []] 

和尾部是輸入列表實際結構尾巴，這樣List.tl l == List.hd (List.tl (tails l))。