generics - Scala解构然后重建一个Iterable

我目前正在 Scala 中实现我自己的 Trie (用于学习/爱好目的)，并且我试图保持它的通用性(以便它可以存储任何可迭代的东西，而不仅仅是字符串)。我的类(class)签名看起来像

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

我已经实现了 contains、+= 和 -=(它扩展了 Set 的可变版本)，但是我在迭代器方面遇到了一些麻烦。我目前的方法让我摸不着头脑，寻找一个优雅的实现。我有一种方法可以遍历所有 TrieNode，并且只给出标记为“有效结尾”的那些。从那里我计划按照父链接来获取各个部分。 (例如，树中的“hello”将存储为标记为结尾的 'o' 节点，父节点为 'l' -> 'l' -> 'e' -> 'h')

现在我的问题。由于我试图保持通用性，因此我无法从“零件”中重建“物品”。所以我对 SO 的人的问题是处理这个问题的最优雅的方法是什么？我应该在构造函数参数中添加一个重建函数吗？ Item 是否应该有不同的边界来强制函数的存在？或者它完全是别的东西？

最佳答案

Item 和 Part 之间存在隐含的关系。您至少需要将 Item 分解为 Part 对象，而要重建则需要反过来。

因此，采用 "hello": String ，您需要让 f("hello") 返回 ('h': Char, "ello": String) 并且您需要反函数 g('h', "ello") 返回 "hello" 。

因此，只要遵循一些规则，任何具有两个此类功能的两种类型都可以。我认为这些规则很容易凭直觉。或多或少是如何使用 head 和 tail 递归分解列表并使用 :: 重建它

您可以使用上下文绑定(bind)为通常的类型提供这些功能。

(编辑)

实际上我不能真正使用上下文绑定(bind)，因为有两个类型参数，但这就是我的想法:

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𝄞

关于generics - Scala解构然后重建一个Iterable，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6715060/