如何从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.sublistfunc,如果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)