我正在查看列表文档。似乎该库未提供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
函数,因为这是一个非常常见的操作。
最佳答案
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
关于list - 如何从ocaml中的列表中获取子列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2710233/