元素在列表中的位置（OCaml）

Question

在OCaml中元素列表中获取元素位置的最快方法是什么？ 我知道如何获得列表中某个元素的“第n个”位置，但是我想知道如果我已经知道这个元素的值，该如何获取这个元素的位置。

Answer 1

我相信最快的方式是最常用的方式：

1. 浏览列表
2. 返回的位置，如果你打所需元素
3. 如果从未被击中，那么这是最坏的情况，并且整个列表被扫描。

的时间复杂度将是O（N）

let index_of e l = 
    let rec index_rec i = function 
    | [] -> raise Not_found 
    | hd::tl -> if hd = e then i else index_rec (i+1) tl 
    in 
    index_rec 0 l 

Answer 2

let rec findi_rec base p l = match l with [] -> raise Not_found | h::_ when p h -> base | _::t -> findi_rec (base+1) p t;; 

let findi p l = findi_rec 0 p l;; 

由于：

# findi (fun x -> x=4) [1;9;3;2;1;4;5;7];; 
- : int = 5