Scala拆解并重构Iterable

Question

Scala拆解并重构Iterable

4

我目前正在实现一个自己的Scala Trie（用于学习/爱好），并且我试图保持它的通用性（以便它可以存储任何可迭代对象，而不仅仅是字符串）。我的类签名如下：

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

我已经实现了contains，+=和-=（它是可变Set的扩展），但我在迭代器方面遇到了一些问题。我的当前方法让我苦思冥想，寻找一个优雅的实现方式。我有一种方法可以遍历所有TrieNodes，并仅发出标记为“有效结尾”的节点。从那里开始，我计划跟随父链接获取各个部分。(例如，在树中存储的“hello”将作为标记为结尾的“o”节点存储，其父亲是'l' -> 'l' -> 'e' -> 'h')。

现在我的问题是，由于我试图保持通用性，我无法从其“部分”重构“Item”。所以我向SO的人们提出的问题是，应该如何优雅地处理这个问题？我应该在构造函数参数中添加重构函数吗？应该不同地限制“Item”以强制存在该函数吗？还是完全不同的东西？

- Dylan

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- huynhjl · Accepted Answer

Item和Part之间存在一种隐含的关系。至少需要将一个Item分解成Part对象，然后进行重构时需要进行反向操作。

因此，对于"hello": String，您需要使f("hello")返回('h': Char, "ello": String)，并且您需要反向函数g('h', "ello")返回"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