How can I build an immutable tree datastructure in Scala?

Question

I am attempting to construct an immutable Trie defined as such:

case class Trie(children: Map[Char, Trie] = Map.empty[Char, Trie], value: Option[String] = None)

With the following extension methods:

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))

My issue at present is with the insert method specifically: I've tried a number of different approaches, but all my attempts fail to return the root of the Trie, i.e. I am unable to insert new nodes in such a way that an entire branch from the root node to leaf is copied along with the newly inserted node.

To further illustrate, the following:

@main def hello: Unit =
  println(new Trie().insert("bot").insert("bat"))

Simply results in: Trie(Map(),Some(bat))

I am new to Scala and FP in general, so I am unsure of best approaches here.

Answer 1

The appears to get at what you're after.

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)))
    }

testing:

Trie().insert("inn").insert("in")
//Trie(Map(i -> Trie(Map(n -> Trie(Map(n -> Trie(Map(),Some(inn))),Some(in))),None)),None)