OCaml - 返回列表的所有前綴的函數

對於[1;2;3]，我想返回[[]; [1]; [1; 2]; [1; 2; 3]]。我已經碰了壁，我需要幫助，這是我迄今所做OCaml - 返回列表的所有前綴的函數

let rev list = 
let rec aux acc = function 
    | [] -> acc 
    | h::t -> aux (h::acc) t in 
aux [] list;; 

let prefixes xs = 
let xs = rev xs in 
let rec xs = function 
    |[] -> [[]] 
    |hd::tl -> xs:: tl in 
xs ;;`

請幫助我，我知道這可能是最的是我迄今所做的是錯的。

來源

2014-11-06 Thanospan

這是我找到的解決方案。雖然它可能不是最好的，因爲我需要在最後反轉列表。

let prefix l = List.rev (List.fold_left (fun acc itt -> ((List.hd acc)@[itt])::acc) [[]] l);;

來源

2014-11-07 00:34:37

你能走我扔你做了什麼，因爲我是真正的新的OCaml – Thanospan 2014-11-07 00:48:26

@Thanospan我會假設你熟悉倍。如果不訪問[this]（http://www.cs.cornell.edu/courses/cs3110/2011sp/recitations/rec05.htm）。所以在List.fold_left中它將是l的一個元素。例子第一次是1，然後是2然後3 ... acc是你現在擁有的，它以[[]]爲空的int列表清單開始。因此，讓我們說，我們在itt = 1然後acc的頭將是[]。我們將該頭連接到itt = 1來製作[1]。 acc將被保存爲[[1]; []]我們讓這個新的acc。所以當fold_left再次迭代使itt = 2時，acc的頭部將會是[1]。 ** next ** – 2014-11-07 02:45:23

我們再次將頭部= [1]連接到[2]。所以我們有[1; 2]，我們將新的acc保存爲[[1; 2]; [1]; []]。所以你可能會看到基本的想法。當itt = 1 [n]，其中l [n]是列表l的第n個位置。我們希望acc的頭部是元素l [0]; l [1]; ..; l [n-1]（包含所有元素直到但不包括l [n]）的列表。然後我們將這兩者結合起來，使我們想要的列表包含所有元素l [0]到l [n]。然後基本上將其添加到acc的頂部。最後，這個列表實際上是相反的，所以我調用List.rev來反轉它。隨意問你是否困惑。 – 2014-11-07 02:54:30

要問的常見問題是如何獲得給定一個函數的列表前綴，該函數返回一個較短列表的所有前綴。

說你的清單是[1; 2; 3]。較短的清單將是[2; 3]。此較短列表的所有前綴是[]，[2]和[2;3]。你怎麼能從這個列表中得到你想要的前綴列表？它看起來相當直接：你只需要將1添加到它們的前面。另外你需要添加一個新的空白前綴。

作爲基本情況，[]的所有前綴列表僅爲[]。

這似乎是一種解決問題的可行方法，但最好的方法是使用List模塊中的函數。由於這看起來像功課，我不確定這是允許的。

我希望這會有所幫助。

作爲一條評論，您的rev函數看起來不錯。但你可能不需要它來解決問題。也許你可以編寫自己的map函數。

來源

2014-11-07 00:10:31

這一個似乎比之前發佈的解決方案簡單得多。請注意0不是尾部遞歸的。

let rec prefixes l = match l with 
     [] -> [] 
    | x::xs -> [x] :: (List.map (fun a -> (x :: a)) (prefixes xs));;

來源

2015-10-21 19:28:30

let rec prefixes = function 
     [] -> [[]] 
    | x::tl -> []::List.map (fun li -> x :: li) (prefixes tl);;

測試：

# prefixes [1];; 
- : int list list = [[]; [1]] 
# prefixes [1;2];; 
- : int list list = [[]; [1]; [1; 2]] 
# prefixes [1;2;3];; 
- : int list list = [[]; [1]; [1; 2]; [1; 2; 3]]

來源

2015-10-21 22:31:58

OCaml - 返回列表的所有前綴的函數

回答

相關問題