listpositionocamlelement

Position of an element in a list


What is the fastest way to get the position of an element in a list of element in OCaml? I know how to get the "nth" position of an element in a list but I would like to know how to get the position of this element if I already know the value.


Solution

  • I believe the fastest is way is the most usual way:

    1. Scan the list
    2. Return the position if you hit the desired element
    3. If never hit, then it is the worst case and entire list is scanned.

    The time complexity will be 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