OCaml에서 해시 테이블을 사용하여 구현하는 방법을 이해하려고 시도했습니다.

Question

Ocaml에서 해시 테이블을 사용하여 시도를 구현하는 방법을 이해하려고합니다. https://www.fun-mooc.fr/에 MOOC "OCaml에서의 기능 프로그래밍 입문"의 연습 문제입니다.

누군가가 내가 명령형 해시 테이블을 사용하여 재귀 적 시도를 구현하는 방법을 이해하도록 도와 주시면 정말 고맙습니다.

과정이 끝났습니다. 이해하기를 원합니다.

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

을에 따르면

이

내가 노력하고있어입니다 (주어진 모듈 GenericTrie 및 모듈 트리는의 템플릿을, 우리는 Hashtbl.Make 펑터를 인스턴스화하고 빈, 조회를 구현하고 삽입했다) 내가 here을 준 대답, 유일한 차이점은 내가 이해에서 대신 Map을 가진 당신은, 그래서 Hashtbl

을 가지고, 당신은 결과 문자열 또는 부울을 저장할 수 있다는 것을 의미 string'a option로 트라이 동료 또는 anyt 그렇지 않으면 우리는 그것에 대해 신경 쓰지 않습니다.

첫째, 당신이 하나를 필요로하는 경우가 이상한 생성자를 사용하여 찾을 수 있기 때문에 나는

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

을 쓴 것이고, 기록은 미래를 위해 도움이 될 것입니다 : 내가 lookup을 단순화

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 
    ;; 

(쓰기 if Module.mem ... then Module.find ... else raise Not_found은 정확히 Module.find ...과 같습니다.)

그러면은 어떨까요?? 알고리즘은 매우 간단하다 :

• 내 문자열의 마지막 문자에 도달하면, 나는
• 없는 경우에 값을 연결, 하나 현재의 문자에 관련된 하나의 자식이 있고 난 재귀 적으로이 지점을 통과 그렇지 않으면이 지사를 만들어야합니다.

어느, OCaml의에서, 제공 : 보조 노트로

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 
    ;; 

---

, 나는 그것이 지속 및 가변 데이터 유형을 혼합 정말 이상하다는 사실을 지적하고 싶습니다. 내 취향이 경우,이 될 것이다 : 두 경우 모두

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 
    ;; 

---

,의이 기능을 인쇄 할 수 있습니다 :

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

:이 출력을해야합니다

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