list - OCaml のリスト内の要素の最後の出現

Question

lがリストであり、要素であると仮定すると、リスト内elemの要素の最後の出現をどのように返すことができますか? 要素が に存在しない場合も -1 を返します。リストを反復するために再帰を使用する方法がよくわかりません...elemll

let rec getLastOccurence l elem = …

Answer 1

let findi x l = 
  let rec loop i n l = 
    match l with 
    | y::tl -> loop (i+1) (if y = x then i else n) tl 
    | [] -> n 
  in 
  loop 0 (-1) l;;

Answer 2

基本的に、要素で見つかった現在のインデックスと最大インデックスを追跡するには、2 つのアキュムレータが必要です。次に、リストの最後まで再帰して、「最大インデックス」値を返します。

let rindex elem = 
  let rec find_index i max_found = function
    | (x::xs) when x = elem -> find_index (i+1) i xs
    | (_::xs) -> find_index (i+1) max_found xs
    | [] -> max_found
  in find_index 0 (-1);;

これは、折りたたみとして非常に簡単に表現することもできます。

let rindex elem ls = 
  let find_index (i, max) elem' = (i+1, if elem' = elem then i else max)
  in snd (fold_left find_index (0, -1) ls);;

Answer 3

これは、リスト内の整数を見つけるための末尾再帰アルゴリズムです。

let find_index elt lst =
  (* Wrap inner function that accepts an accumulator to keep the interface clean *)
  let rec find_it elt acc = function
    | hd :: tl when elt = hd -> acc (* match *)
    | hd :: tl -> find_it elt (acc + 1) tl (* non-match *)
    | _ -> raise Not_found (* end of list *)
  in find_it elt 0 lst (* call inner function with accumulator starting at 0 *)
;;