元素在列表中的位置（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