在OCaml中具有特定長度的列表的列表

我在想如何編寫一個函數：'a list*int -> 'a list*list，它將給定列表轉換爲給定最大長度的列表列表。在OCaml中具有特定長度的列表的列表

例如：segments([1;2;3;4;5;6;7;8;9], 2) => [ [1;2]; [3;4]; [5;6]; [7;8]; [9] ]

2012-03-20 João Oliveira

這聽起來像功課。如果你顯示了一些你嘗試過的代碼無法正常工作，這會有所幫助。 – 2012-03-20 22:00:35

這是一個tail-遞歸溶液：

let segments xs n = 
    let rec loop n xs (count, elem) acc = 
     match xs with 
     | x::xs' when count < n -> loop n xs' (count+1, x::elem) acc 
     | x::xs' -> loop n xs' (1, [x]) ((List.rev elem)::acc) 
     | [] -> List.rev ((List.rev elem)::acc) in 
    loop n xs (0, []) []

的想法是保持一個累加器，用於創建當前段和另一累加器用於存儲段的列表。

來源

2012-03-20 22:35:55 pad

完美地工作，這是一個很好的解決方案，謝謝 – 2012-03-20 22:57:50

你的解決方案是好的，但我可以看到，我們可以改善。由於長度是給定的，我們不需要在函數循環中使用它。如下：令段（T，N）= \t讓REC環噸（計數，ELEM）ACC = 匹配噸與 | x :: t'當計數< n ->循環t'（計數+ 1，x :: elem）acc | x :: t' - > loop t'（1，[x]）（（List.rev elem）:: acc） | [] - > List.rev（（List.rev elem）:: acc） \t in loop t（0，[]）[] ;; – 2012-03-22 11:03:05

這是瑣碎BatList.split_at：

let rec segments list n = 
    try let head, tail = BatList.split_at n list in 
     head :: segments tail n 
    with Invalid_index _ -> [ list ]

如果你沒有進入電池，實現split_at是相當容易的。

來源

2012-03-20 22:20:20

請注意，這個解決方案並不是尾遞歸的，而且實際上是以很快的速度吞噬堆棧，因爲遞歸是嵌入在try ...內部的。 – 2012-03-21 11:19:12

我不同意使用BatList應該用於此。當然，如果你使用那些習慣使用這些庫的人進行編程，這很好（可能你是，那麼請不要這麼做！）。但在「經典」的情況下，這更自然地用一個簡單的尾部遞歸函數完成。（你可以摺疊追加來得到一些無用的東西，但在實踐中效果並不理想，並且有一個更好的基於累加器的解決方案，可以實現簡單的基於尾部呼叫的實現。）

來源

2012-03-20 22:24:43

的以前的正確答案（按墊）的改進版本：

let segments (xs,n) = 
    let rec loop xs (count, elem) acc = 
     match xs with 
     | x::xs' when count < n -> loop xs' (count+1, x::elem) acc 
     | x::xs' -> loop xs' (1, [x]) ((List.rev elem)::acc) 
     | [] -> List.rev ((List.rev elem)::acc) in 
    loop xs (0, []) [];;

來源

2012-03-22 11:07:37

在OCaml中具有特定長度的列表的列表

回答

相關問題