泛型 – Scala解构然后重构一个Iterable

发布时间：2020-12-16 19:24:15 所属栏目：安全来源：网络整理

导读：我正在努力在 Scala中实现我自己的 Trie(用于学习/爱好目的),并且我试图保持它的通用性(这样它可以存储任何可迭代的,而不仅仅是字符串).我的班级签名看起来像 class Trie[Item % Iterable[Part],Part](items: Item*) extends Set[Item] 我已经有contains,=和

我正在努力在 Scala中实现我自己的 Trie(用于学习/爱好目的),并且我试图保持它的通用性(这样它可以存储任何可迭代的,而不仅仅是字符串).我的班级签名看起来像

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

我已经有contains,=和 – =实现(它扩展了Set的可变版本),但我在使用迭代器时遇到了一些麻烦.我目前的方法让我摸不着头脑,寻找一个优雅的实现.我有办法迭代所有的TrieNodes,只给出标记为“有效结尾”的TrieNodes.从那里我计划按照父链接获取各个部分. (例如,树中的“hello”将被存储为标记为结尾的“o”节点,父级为“l” – >“l” – >“e” – >“h”)

现在我的问题.由于我试图保持通用,我无法从其“部件”重建“项目”.所以我向SO的人提出的问题是处理这个问题的最优雅方式是什么？我应该在构造函数参数中添加重建函数吗？ Item应该以不同的方式强制执行函数的存在？或者它完全是另一回事？

解决方法

Item和Part之间存在隐含的关系.您至少需要将Item分解为Part对象并重建,您需要执行相反的操作.

所以拿“hello”：String,你需要有f(“hello”)return(‘h’：Char,“ello”：String)你需要反函数g(‘h’,“ello”)return“你好”.

因此,只要遵循一些规则,任何具有两个这样的函数的两种类型都可以.我认为规则很容易直觉.你或多或少地使用头部和尾部递归地分解列表并使用::重建它

您可以使用上下文绑定来为常规类型提供这些函数.

(编辑)

实际上我不能真正使用上下文绑定,因为有两个类型参数,但这是我的想法：

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,e,h)
nat1.rebuilt   // hello

val nat2 = new NotATrie[String,Int]("helloud834udd1e")
nat2.brokenUp // List(119070,111,108,101,104)
nat2.rebuilt  // hello                        （编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!