Scala деконструировать, а затем реконструировать Iterable - PullRequest
Новая
       8

Scala деконструировать, а затем реконструировать Iterable

4 голосов
/ 16 июля 2011

В настоящее время я работаю над реализацией моей собственной Trie в Scala (для целей обучения / хобби), и я пытаюсь сделать ее универсальной (чтобы она могла хранить что угодно, а не только строки).).Моя подпись класса выглядит так: 

class Trie[Item <% Iterable[Part], Part](items: Item*) extends Set[Item]

У меня уже есть содержит, + = и - = реализовано (это расширяет изменяемую версию Set), но у меня возникли некоторые проблемы с итератором.Мой текущий подход заставляет меня почесать голову в поисках изящной реализации.У меня есть способ перебрать все узлы TrieNode и выделить только те, которые помечены как «действительные окончания».Оттуда я планирую перейти по родительским ссылкам, чтобы получить отдельные части.(например, «привет» в дереве будет сохранен как узел «o», помеченный как окончание, с родительским «l» -> «l» -> «e» -> «h»)

Теперьмоя проблема.Поскольку я пытаюсь сделать вещи общими, у меня нет возможности восстановить «Предмет» из его «Частей».Итак, мой вопрос к людям из SO: какой самый изящный способ справиться с этим?Должен ли я добавить функцию восстановления к аргументам конструктора?Должен ли Item быть ограничен по-другому, чтобы обеспечить наличие функции?Или это что-то совсем другое?

1 Ответ

1 голос
/ 16 июля 2011

Существует неявная связь между Предметом и Частью. Как минимум, вам нужно разложить Предмет на объекты Части, а для восстановления вам нужно сделать обратное.

Итак, взяв "hello": String, вам нужно иметь f("hello") return ('h': Char, "ello": String) и обратную функцию g('h', "ello") return "hello".

Таким образом, любые два типа с двумя такими функциями будут работать при условии соблюдения некоторых правил. Я думаю, что правила легко интуитивно понятны. Это более или менее то, как вы рекурсивно разлагаете список, используя head и tail, и перестраиваете его, используя ::

Вы можете использовать связанный контекст для предоставления этих функций для обычного типа.

(редактировать)

На самом деле я не могу использовать контекстную границу, потому что есть два типа параметров, но это то, что я имел в виду: 

trait R[Item, Part] {
  def decompose(item: Item): (Part, Item)
  def recompose(item: Item, part: Part): Item
  def empty: Item
}

class NotATrie[Item, Part](item: Item)(implicit rel: R[Item, Part]) {
  val brokenUp = {
    def f(i: Item, acc: List[Part] = Nil): List[Part] = {
      if (i == rel.empty) acc
      else {
        val (head, tail) = rel.decompose(i)
        f(tail, head :: acc)
      }
    }
    f(item)
  }

  def rebuilt =  (rel.empty /: brokenUp)( (acc, el) => rel.recompose(acc, el) )
}

Затем мы предоставляем несколько неявных объектов: 

implicit object string2R extends R[String, Char] {
  def decompose(item: String): (Char, String) = (item.head, item.tail)
  def recompose(item: String, part: Char): String = part + item
  def empty: String = ""
}

implicit object string2RAlt extends R[String, Int] {
  def decompose(item: String): (Int, String) = {
    val cp = item.codePointAt(0)
    val index = Character.charCount(cp)
    (cp, item.substring(index))
  }
  def recompose(item: String, part: Int): String = 
    new String(Character.toChars(part)) + item
  def empty: String = ""
}

val nat1 = new NotATrie[String, Char]("hello")
nat1.brokenUp  // List(o, l, l, e, h)
nat1.rebuilt   // hello

val nat2 = new NotATrie[String, Int]("hello\ud834\udd1e")
nat2.brokenUp // List(119070, 111, 108, 108, 101, 104)
nat2.rebuilt  // hello?
...