Создание char Trie в OCaml - PullRequest
Новая
       24

Создание char Trie в OCaml

0 голосов
/ 24 сентября 2018

Я пытаюсь построить начальную структуру Trie в OCaml, где ребра - это символ.Таким образом, строка «ESK» будет отображаться как:

[('E', [('S', [('K', [])])])]

Мое определение для этого: 

type trie = Trie of (char * trie) list

Однако, при реализации функции addс: 

 let rec add_string str =
    let key = String.get str 0 in
    if String.length str = 1 then
      (key, empty_trie) :: []
    else
      (key, add_string (tail str)) :: []

для add (tail str) компилятор дает мне: 

Error: This expression has type (char * trie) list
       but an expression was expected of type trie

Я немного озадачен этим, поскольку я не определил trie как (char * trie) list?

tail это просто let tail str = String.slice str 1 (String.length str) и empty_trie это let empty_trie = Trie([])

Ответы [ 2 ]

0 голосов
/ 24 сентября 2018

Обратите внимание, что более идиоматическим способом написания функции будет 

let rec add_string str =
  let key = str.[0] in
  if String.length str = 1 then
    Trie [key, empty_trie]
  else
    Trie [key, add_string (tail str)]

Тогда с add_string остаются две проблемы: сначала она перераспределяет новую строку на каждой итерации.Проще и эффективнее отслеживать текущую позицию: 

let add_string str =
  let rec add_string_aux pos str =
    if pos = String.length str then empty_trie
    else
      let key = str.[pos] in
      Trie [key, add_string_aux (pos+1) str] in
  add_string_aux 0 str

Вторая проблема заключается в том, что функция имеет неправильное имя, поскольку она не добавляет строку в существующий файл, а создает файл изстрока: from_string или of_string могут быть более подходящими именами.

0 голосов
/ 24 сентября 2018

Решено.Trie должно быть явно использовано: 

let rec add_string str =
  let key = String.get str 0 in
  if String.length str = 1 then
    (key, empty_trie) :: []
  else
    (key, Trie (add_string (tail str))) :: []

Это приведет к add_string "ESK" выдаче:

(char * trie) list = [('E', Trie [('S', Trie [('K', Trie [])])])]

...