如何从ocaml中的列表中获取子列表 [英] how to get a sub list from a list in ocaml
问题描述
我正在查看列表文档.似乎该库未提供sublist
函数.
I'm looking at the List documentation. It seems the library does not provide a sublist
function.
我正在尝试从 i 到 j 的元素列表.现在,我必须将其编写为:
I'm trying to get list of elements from i to j. Now I have to write it as:
let rec sublist list i j =
if i > j then
[]
else
(List.nth list i) :: (sublist list (i+1) j)
这是非常简洁的,但是我在质疑List.nth
的效率,因为如果它是 O(n),我宁愿以一种不太简洁的方式编写它.
which is quite concise but I'm questioning the efficiency of List.nth
, because if it's O(n), I would rather have to write it in a less concise way.
我想知道为什么如果List.nth
不是 O(1),他们为什么不提供List.sublist
func,因为这是一个非常常见的操作..
I'm wondering why didn't they provide List.sublist
func, if List.nth
is not O(1), because it's such a quite common operation..
推荐答案
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
中的所有元素.
The above is more or less a deforested version of newacct's solution. newacct's solution allocates an intermediate list (drop i list
), which is possible for the compiler to optimize away in Haskell but much harder in ML. Therefore his version is perfectly fine for a Haskell function and marginally sub-optimal for an ML one. The difference between the two is only a constant factor: both are O(e). zrr's version is O(length(l)) since List.filteri
doesn't know that f
only returns false
after a while, it calls it for all elements in l
.
我不太愿意让b
变为负数,但没有的版本则更加复杂.
I'm not very happy to let b
go negative but the version where it doesn't is more complicated.
如果您有兴趣的话,您可以在很多参考资料中提及: http://homepages.inf.ed.ac.uk/wadler/topics/deforestation.html
One reference among quite a few for deforestation if you're interested: http://homepages.inf.ed.ac.uk/wadler/topics/deforestation.html
这篇关于如何从ocaml中的列表中获取子列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!