Essayer de comprendre comment implémenter Essais avec des tables de hachage dans OCaml

Question

J'essaie de comprendre comment implémenter Tries avec des tables de hachage dans Ocaml. C'est l'exercice W06 04 du MOOC "Introduction à la programmation fonctionnelle en OCaml" au https://www.fun-mooc.fr/. J'apprécie vraiment si quelqu'un peut m'aider à comprendre comment implémenter les essais récursifs en utilisant les tables de hachage impératives.

Le cours est terminé, je veux juste comprendre.

C'est ce que je suis en train (module GenericTrie et le modèle du module a été donné Trie, nous avons dû instancier foncteur Hashtbl.Make et mettre en œuvre vide, recherche et insérer):

module type GenericTrie = sig 
    type 'a char_table 
    type 'a trie = Trie of 'a option * 'a trie char_table 
    val empty : unit -> 'a trie 
    val insert : 'a trie -> string -> 'a -> 'a trie 
    val lookup : 'a trie -> string -> 'a option 
end 

module CharHashedType = struct 
    type t = char 
    let equal a b = a = b 
    let hash a = Hashtbl.hash a 
end 

module CharHashtbl = Hashtbl.Make(CharHashedType) 

module Trie : GenericTrie with type 'a char_table = 'a CharHashtbl.t = 
    struct 
    type 'a char_table = 'a CharHashtbl.t 
    type 'a trie = Trie of 'a option * 'a trie char_table 

    let empty() = 
     Trie (None, CharHashtbl.create 10) 
    ;; 

    let lookup trie w = 
     let len = String.length w in 
     let rec lookup' trie' idx = 
     if idx >= len then let Trie (x, _) = trie' in x 
     else 
      let Trie (_, table) = trie' in 
      if CharHashtbl.mem table w.[idx] then 
      lookup' (CharHashtbl.find table w.[idx]) (idx + 1) 
      else raise Not_found 
     in 
     lookup' trie 0 
    ;; 

    let insert trie w v = 

    ;; 
    end 

Answer 1

Selon le j'ai répondu here, la seule différence est qu'au lieu d'avoir un Map vous avez un Hashtbl

Alors, d'après ce que je comprends, vos associés TRIE à un string un 'a option ce qui signifie que vous pouvez stocker la chaîne résultante ou un booléen ou anyt Hing d'autre mais nous ne nous soucions pas de cela.

D'abord, je l'aurais écrit

type 'a trie = {value : 'a option; 
       children : 'a trie char_table} 

Parce que je trouve étrange d'utiliser un constructeur si vous avez juste besoin d'un et le dossier aiderai pour l'avenir:

module Trie : GenericTrie with type 'a char_table = 'a CharHashtbl.t = struct 
    type 'a char_table = 'a CharHashtbl.t 
    type 'a trie = {value : 'a option; 
        children : 'a trie char_table} 

    let empty() = 
    {value = None; children = CharHashtbl.create 10} 
    ;; 


    let lookup trie w = 
    let len = String.length w in 
    let rec lookup' {value; children} idx = 
     if idx >= len then value 
     else 
     let char = w.[idx] in 
     let child = CharHashtbl.find children char in 
     lookup' child (idx + 1) 
    in 
    lookup' trie 0 
    ;; 

I simplifié lookup (Notez que l'écriture if Module.mem ... then Module.find ... else raise Not_found est strictement équivalent à Module.find ...)

Ensuite, qu'en est-il de insert? L'algorithme est assez simple:

• si je suis arrivé à la dernière lettre de ma chaîne, je lui associez la valeur
• sinon, soit il y a un enfant associé à la lettre actuelle et je vais récursive dans cette branche ou il n'y a pas et j'ai besoin de créer cette branche.

qui, en OCaml, donne:

let insert trie w v = 
    let len = String.length w in 
    let rec aux trie idx = 
     if idx >= len then {trie with value = Some v} 
     else 
     let char = w.[idx] in 
     let child = try CharHashtbl.find trie.children char 
      with Not_found -> empty() in 
     let child' = aux child (idx + 1) in 
     CharHashtbl.add trie.children char child'; 
     trie 
    in aux trie 0 
    ;; 

---

Comme une note de côté, je voudrais souligner le fait que c'est vraiment étrange de mélanger les types de données persistantes et mutables. Ma préférence, dans ce cas, ne serait-ce:

module type GenericTrie = sig 
    type 'a char_table 
    type 'a trie = {mutable value : 'a option; 
        children : 'a trie char_table} 
    val empty : unit -> 'a trie 
    val insert : 'a trie -> string -> 'a -> unit 
    val lookup : 'a trie -> string -> 'a option 
end;; 

module CharHashedType = struct 
    type t = char 
    let equal a b = a = b 
    let hash a = Hashtbl.hash a 
end;; 

module CharHashtbl = Hashtbl.Make(CharHashedType) 

module Trie : GenericTrie with type 'a char_table = 'a CharHashtbl.t = struct 
    type 'a char_table = 'a CharHashtbl.t 
    type 'a trie = {mutable value : 'a option; 
        children : 'a trie char_table} 

    let empty() = 
    {value = None; children = CharHashtbl.create 10} 
    ;; 

    let lookup trie w = 
    let len = String.length w in 
    let rec lookup' {value; children} idx = 
     if idx >= len then value 
     else 
     let char = w.[idx] in 
     let child = CharHashtbl.find children char in 
     lookup' child (idx + 1) 
    in 
    lookup' trie 0 
    ;; 

    let insert trie w v = 
    let len = String.length w in 
    let rec aux trie idx = 
     if idx >= len then trie.value <- Some v 
     else 
     let char = w.[idx] in 
     let child = try CharHashtbl.find trie.children char 
      with Not_found -> 
      let child = empty() in 
      CharHashtbl.add trie.children char child; 
      child 
     in 
     aux child (idx + 1) 
    in aux trie 0 
    ;; 

---

Dans les deux cas, nous allons l'imprimer avec cette fonction:

let (t : string Trie.trie) = Trie.empty();; 

let rec pp fmt trie = 
    let open Trie in 
    let {value; children} = trie in 
    Format.fprintf fmt "@[<v 1>"; 
    (match value with 
    | None -> Format.fprintf fmt "None" 
    | Some s -> Format.fprintf fmt "Some %s" s 
); 
    CharHashtbl.iter (fun char trie -> 
    Format.fprintf fmt "@ %c@ %a" char pp trie 
) children; 
    Format.fprintf fmt "@]" 

let() = 
    Trie.insert t "foo" "foo"; 
    Trie.insert t "fol" "fol"; 
    Trie.insert t "far" "far"; 
    Format.printf "%a@." pp t 

Je vais avoir cette sortie:

None 
f 
None 
    o 
    None 
    o 
    Some foo 
    l 
    Some fol 
    a 
    None 
    r 
    Some far