How can I build an immutable tree datastructure in Scala?
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)