如何从 ocaml 中的列表中获取子列表

Question

我正在查看 List 文档。图书馆似乎没有提供

sublist

功能。

我正在尝试获取从 i 到 j 的元素列表。现在我必须把它写成：

let rec sublist list i j =
  if i > j then
    []
  else
    (List.nth list i) :: (sublist list (i+1) j)

这很简洁，但我质疑

List.nth

的效率，因为如果它是O(n)，我宁愿不得不以不太简洁的方式写它。

我想知道为什么他们不提供

List.sublist

函数，如果

List.nth

不是 O(1)，因为这是一个非常常见的操作..

Answer 1

let rec sublist b e l = 
  match l with
    [] -> failwith "sublist"
  | h :: t -> 
     let tail = if e=0 then [] else sublist (b-1) (e-1) t in
     if b>0 then tail else h :: tail
;;

sublist 3 5 [1;2;3;4;5;6;7;8;9] ;;
- : int list = [4; 5; 6]

以上或多或少是newacct解决方案的森林砍伐版本。 newacct 的解决方案分配一个中间列表 (

drop i list

)，编译器可以在 Haskell 中优化它，但在 ML 中更难优化。因此，他的版本对于 Haskell 函数来说非常好，对于 ML 函数来说略微次优。两者的区别只是一个常数因子：都是O(e)。 zrr 的版本是 O(length(l)) 因为

List.filteri

不知道

f

只在一段时间后返回

false

，所以它为

l

中的所有元素调用它。

我不太乐意让

b

变负，但它不负的版本更复杂。

如果您有兴趣，可以参考很多森林砍伐：http://homepages.inf.ed.ac.uk/wadler/topics/deforestation.html

Answer 2

首先尝试编写

take

（前 n 项）和

drop

（除前 n 项之外的所有内容）函数（就像在 Haskell 中一样）。那么

sublist i j lst

就是

take (j-i) (drop i lst)

Answer 3

这比使用 OCaml 的标准库要难一些——标准库有点稀疏。如果您使用扩展标准库之一，它会变得更容易。以 Core 为例，你可以这样写：

let sublist list low high =
   List.filteri l ~f:(fun i _ -> i >= low && pos < high)

我想 extlib/batteries 也可能有类似的东西。

Answer 4

虽然 Pascal 提供的答案为

List.sublist

实现了一个很好的候选者，但正确的答案是您最好使用列表数组。 Array 模块实现了您可能使用的

Array.sub

功能。

虽然在 C++ 或 Perl 等许多命令式语言中，列表和数组之间基本上没有区别，但在 OCaml 中却不同，其中：

• 列表更适合递归处理和顺序访问，即通常更适合作为递归函数参数的数组，并且您通常想查看列表的所有元素。

• 数组更适合随机访问、结构更改（例如排序）或数值计算。

Answer 5

let rec sublist (lst : int list) (start : int) (stop : int) : int list =
  match lst with
  | [] -> [] 
  | x::rest when start = 0 && stop >= 0 -> x::sublist rest start (stop-1)
  | x::rest when start = 0 && stop = 0 -> sublist rest start stop
  | x::rest -> sublist rest (start-1) (stop-1)
;;

when 就像 else 语句一样工作