En supposant l est une liste et elem est un élément, comment puis-je retourner la dernière occurrence de l'élément elem dans la liste l? Renvoie également -1 si l'élément n'existe pas dans l. Je ne comprends pas tout à fait comment utiliser la récursivité pour itérer dans la liste ...Dernière occurrence d'élément dans une liste dans OCaml
let rec getLastOccurence l elem = …
Ceci est un algorithme récursif de queue pour trouver un entier dans une liste:
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 *)
;;
Je ne comprends pas la ligne | _ -> raise Not_found –
Les deux premières options de correspondance capturent le cas lorsqu'il existe un élément head et tail, en utilisant l'opérateur contre (:). Le symbole _ est une convention qui dit: "Ignore ce match". Le pattern correspond à n'importe quoi, mais comme les deux premiers capturent tout de a :: b à a :: nothing, le dernier est utilisé pour attraper la situation où nous avons itéré dans toute la liste sans trouver de correspondance. En relisant votre question, vous voulez changer "raise Not_found" à -1. –
Notez que vous pouvez également utiliser "| [] -> raise Not_found" pour le motif final. Aucun ne se lierait à une variable. Ils sont effectivement équivalents. –
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;;
Fondamentalement , vous avez besoin de deux accumulateurs pour garder trace de l'index actuel et de l'index maximum trouvé pour l'élément. Ensuite, vous revenez à la fin de la liste et renvoyez la valeur "index maximum".
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);;
Cela peut aussi être exprimé assez simplement comme un pli:
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);;
voulez-vous dire « indice de » la dernière occurrence? parce que sinon les valeurs de retour (l'élément et -1) ne sont pas du même type – newacct
oui c'est ce que je veux dire .... –