Piles, files et tables de hachage

Dans l'ordre 'c', 'b', 'a' : c'est une pile (LIFO), le dernier empilé sort en premier. (Avec une file, l'ordre serait 'a', 'b', 'c'.)

let somme_file f =
  let s = ref 0 in
  while not (Queue.is_empty f) do
    s := !s + Queue.pop f
  done;
  !s

On dépile tant que la file n'est pas vide, en accumulant. À la fin, la file est vide (effet de bord) et l'on renvoie la somme. La discipline FIFO n'importe pas ici : on visite tous les éléments.

let valeur t cle =
  match Hashtbl.find_opt t cle with
  | None -> 0
  | Some v -> v

find_opt évite l'exception Not_found de find : on filtre None/Some v et l'on choisit une valeur par défaut pour l'absence. C'est l'usage le plus sûr.

let equilibre s =
  let p = Stack.create () in
  let ok = ref true in
  for i = 0 to String.length s - 1 do
    if s.[i] = '(' then Stack.push '(' p
    else if s.[i] = ')' then
      if Stack.is_empty p then ok := false
      else ignore (Stack.pop p)
  done;
  !ok && Stack.is_empty p

Chaque '(' est empilé ; chaque ')' doit pouvoir dépiler une parenthèse ouvrante en attente — sinon il y a une fermante de trop (ok := false). À la fin, la pile doit être vide (sinon il reste des ouvrantes). (ignore jette la valeur dépilée, dont on n'a pas l'usage.)

let renverse_file f =
  let p = Stack.create () in
  while not (Queue.is_empty f) do
    Stack.push (Queue.pop f) p
  done;
  while not (Stack.is_empty p) do
    Queue.push (Stack.pop p) f
  done

On vide la file dans une pile : l'ordre s'inverse (FIFO puis LIFO). On revide la pile dans la file : les éléments y reviennent renversés. La file f est modifiée sur place ; la fonction renvoie ().

let occurrences l =
  let t = Hashtbl.create 16 in
  let rec parcours l =
    match l with
    | [] -> ()
    | mot :: reste ->
        (match Hashtbl.find_opt t mot with
         | None -> Hashtbl.add t mot 1
         | Some n -> Hashtbl.remove t mot; Hashtbl.add t mot (n + 1));
        parcours reste
  in
  parcours l;
  t

Pour chaque mot, on consulte sa valeur : absent, on l'ajoute avec 1 ; présent avec n, on le retire puis rajoute avec n + 1 (pas de remplacement au programme). On maintient ainsi une liaison unique par clé.

let premier_doublon l =
  let vus = Hashtbl.create 16 in
  let rec parcours l =
    match l with
    | [] -> None
    | x :: reste ->
        if Hashtbl.mem vus x then Some x
        else begin
          Hashtbl.add vus x true;
          parcours reste
        end
  in
  parcours l

La table vus joue le rôle d'un ensemble : on y note chaque élément déjà vu (la valeur true importe peu, seule compte la présence de la clé). Dès qu'un élément est déjà présent, c'est le premier doublon. Coût $\Theta (n)$ en moyenne, contre $\Theta (n^2)$ avec une recherche par liste.

let memo = Hashtbl.create 100

let rec fibo n =
  if n < 2 then n
  else
    match Hashtbl.find_opt memo n with
    | Some v -> v
    | None ->
        let v = fibo (n - 1) + fibo (n - 2) in
        Hashtbl.add memo n v;
        v

Avant de calculer fibo n, on regarde s'il est déjà en cache. Sinon on le calcule une fois et on l'enregistre. Chaque valeur n'est ainsi calculée qu'une fois : on passe du coût exponentiel de la version naïve (chapitre 3) à un coût linéaire. C'est la mémoïsation — la programmation dynamique appliquée par cache.

let evalue jetons =
  let p = Stack.create () in
  let traite j =
    match j with
    | Nombre n -> Stack.push n p
    | Add -> let b = Stack.pop p in let a = Stack.pop p in Stack.push (a + b) p
    | Mul -> let b = Stack.pop p in let a = Stack.pop p in Stack.push (a * b) p
  in
  List.iter traite jetons;
  Stack.pop p

On empile chaque nombre ; à chaque opérateur, on dépile les deux derniers opérandes, on calcule, et on rempile le résultat. À la fin, la pile contient l'unique résultat. C'est le principe d'une calculatrice à pile — et un classique d'usage conjoint des piles (chapitre 8), des types sommes (chapitre 3) et des listes (chapitre 2).

let plus_frequent t =
  let meilleur = ref "" and maxi = ref 0 in
  Hashtbl.iter
    (fun mot n -> if n > !maxi then begin maxi := n; meilleur := mot end)
    t;
  !meilleur

Hashtbl.iter applique la fonction à chaque liaison (mot, n) ; on retient au passage le maximum dans deux références. L'ordre de parcours d'une table n'est pas spécifié, mais peu importe pour chercher un maximum. (Sur une table vide, la fonction renvoie "" ; on pourrait préférer un string option.)