4

私は現在、Scalaで自分のTrieを実装することに取り組んでおり（学習/趣味の目的で）、それを汎用的に維持しようとしています（文字列だけでなく、反復可能なものをすべて保存できるようにするため）。私のクラスの署名は次のようになります

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

私はすでにcontains、+ =および-=を実装しています（これはSetの可変バージョンを拡張しています）が、イテレーターに問題があります。私の現在のアプローチでは、優雅な実装を探して頭を悩ませています。すべてのTrieNodeを反復処理し、「有効な終了」としてマークされているものだけを放出する方法があります。そこから、親のリンクをたどって個々のパーツを入手する予定です。（たとえば、ツリーの「hello」は、親'l'->'l'->'e'->'h'を使用して、終了としてマークされた'o'ノードとして格納されます）

今私の問題。私は物事を一般的にしようとしているので、「パーツ」から「アイテム」を再構築する方法がありません。それで、SOの人々への私の質問は、これを処理するための最も優雅な方法は何でしょうか？コンストラクター引数に再構成関数を追加する必要がありますか？Item関数の存在を強制するために、別の方法で境界を設定する必要がありますか？それともまったく別のものですか？

4

1 に答える 1

1

アイテムとパーツの間には暗黙の関係があります。少なくとも、アイテムをパーツオブジェクトに分解し、再構築するにはその逆を行う必要があります。

したがって、をとる"hello": Stringと、f("hello")return('h': Char, "ello": String)が必要であり、逆関数g('h', "ello")returnが必要"hello"です。

したがって、いくつかのルールが守られている限り、そのような関数が2つある2つのタイプでも機能します。ルールは直感的に理解しやすいと思います。headを使用してリストを再帰的に分解し、を使用してリストtailを再構築する方法は、多かれ少なかれです。::

コンテキストバインドを使用して、通常のタイプにこれらの関数を提供できます。

（編集）

実際には、2つの型パラメーターがあるため、コンテキストバインドを実際に使用することはできませんが、これは私が念頭に置いていたものです。

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
于 2011-07-16T05:48:29.753 に答える