Есть ли реализация Trie в sml с использованием чисел? - PullRequest
Новая
       15

Есть ли реализация Trie в sml с использованием чисел?

0 голосов
/ 21 июня 2019

Есть ли в sml реализация trie, которая берет число из ввода, затем разбивает число на его цифры и вставляет их в trie?Это уже разработанная структура или какой-то уже существующий код, который я мог бы использовать?Есть ли у него функция поиска?

1 Ответ

1 голос
/ 21 июня 2019

Быстрый поиск «стандартного мл-три» дает следующие два главных результата:

  1. github.com / cannam / sml-trie , который не является 'написано таким образом, что помогает образовательным целям.Основная часть реализации находится в TrieMapFn функторе , который параметризует как ключ, так и типы элементов, так что вы можете специализировать это для некоторого числового типа.

  2. github.com / jlao / sml-trie , который представляет собой один файл, который значительно легче переварить.Эта реализация предполагает, что ключи являются строками.Вы можете либо a) адаптировать это, чтобы использовать вместо них числа - в конце концов, это explode строки, поэтому во внутренних структурах есть просто списки char, которые также могут быть спискамииз int - или b) построить оболочку вокруг этого, которая преобразует число (при условии, что ваши числа имеют некоторое каноническое представление строки) в string перед вставкой и поиском.

Например, если ваши номера были int: 

(* Include jlao/sml-trie here. *)

signature NUMBER_DICT =
sig
  type key = int            (* concrete *)
  type 'a entry = key * 'a  (* concrete *)
  type 'a dict              (* abstract *)

  val empty : 'a dict
  val lookup : 'a dict -> key -> 'a option
  val insert : 'a dict * 'a entry -> 'a dict
  val toString : ('a -> string) -> 'a dict -> string
end

structure NumberTrie :> NUMBER_DICT =
struct
  type key = int
  type 'a entry = key * 'a
  type 'a dict = 'a Trie.dict  (* a string-based DICT *)

  val empty = Trie.empty
  fun lookup trie key = Trie.lookup trie (Int.toString key)
  fun insert (trie, (key, value)) = Trie.insert (trie, (Int.toString key, value))
  val toString = Trie.toString
end

Поскольку DICT в jlao имеет конкретный тип ключа, вы должны сделать новую подпись для каждой структуры, которая изменяет тип ключа,Это не так универсально и предлагает нам преобразовать эту Trie структуру в функтор, который принимает в качестве параметра тип ключа.Если ваша цель - исследовать построение функторов в модульной системе, это может быть предпочтительнее.

...