斯卡拉解構然後重建一個可迭代的

Question

我目前正在Scala中實現我自己的Trie（用於學習/愛好的目的），我試圖保持它的通用性（以便它可以存儲任何Iterable，而不僅僅是字符串）。我班的簽名看起來像

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

我已經有包含，+ =和 - =實現（它的擴展設置的可變版本），但我有一些麻煩的迭代器。我目前的做法讓我撓頭尋找一個優美的實現。我有一種方法可以遍歷所有TrieNodes，並且只發布標記爲「有效結尾」的那些。從那裏我打算按照父母的鏈接來獲得個別部分。 （如「你好」樹將被存儲爲標記爲結尾的「O」節點，父「L」 - >「1」 - >「E」 - >「H」）

現在我的問題。由於我試圖保持通用性，所以我無法從其「零件」重建「項目」。所以我對SO的人的問題是什麼纔是處理這個問題的最優雅的方式？我應該爲構造函數參數添加重構函數嗎？ Item應該以不同的方式強制執行函數的存在嗎？還是完全是另一回事？

Answer 1

項目與零件之間存在隱含的關係。至少你需要將一個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