我正在嘗試構建一個不可變的 Trie，定義如下：
case class Trie(children: Map[Char, Trie] = Map.empty[Char, Trie], value: Option[String] = None)
使用以下擴展方法：
extension (t: Trie)
def addAll(words: Seq[String]): Trie =
words.foldLeft(new Trie())(_.insert(_))
def insert(word: String): Trie =
var cur = t
word.foreach(c => {
if !cur.children.contains(c) then
cur = cur.copy(children = cur.children (c -> new Trie()))
end if
cur = cur.children.get(c).get
})
cur.copy(value = Some(word))
我目前的問題是insert具體的方法：我嘗試了許多不同的方法，但是我所有的嘗試都未能回傳 Trie 的根，即我無法插入新節點，使得整個分支從將根節點與新插入的節點一起復制到葉子。
為了進一步說明，以下：
@main def hello: Unit =
println(new Trie().insert("bot").insert("bat"))
簡單的結果是： Trie(Map(),Some(bat))
我一般是 Scala 和 FP 的新手，所以我不確定這里的最佳方法。
uj5u.com熱心網友回復：
似乎得到了你所追求的。
case class Trie(children : Map[Char, Trie] = Map()
,value : Option[String] = None):
def insert(word: String, index: Int = 0): Trie =
word.lift(index).fold(copy(value=Some(word))){c =>
copy(children (c -> children.getOrElse(c,Trie()).insert(word, index 1)))
}
測驗：
Trie().insert("inn").insert("in")
//Trie(Map(i -> Trie(Map(n -> Trie(Map(n -> Trie(Map(),Some(inn))),Some(in))),None)),None)
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/412158.html
標籤：