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

Question

我正在查看列表文档。似乎该库未提供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不是O(1)，他们为什么不提供 List.nth函数，因为这是一个非常常见的操作。

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