在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中具有特定长度的列表的列表

回答

相关问题