Scala Trie

Scala Trie

case class Trie(v: Option[String], m: Map[Char, Trie])

def addInner(t: Trie, s: List[Char], p: String): Trie = s match {
    case c::cs => Trie(t.v, t.m.updated(c, addInner(t.m.getOrElse(c, Trie(Some(p + c), Map.empty)), cs, p + c) ))
    case Nil => t
  }

def add(t: Trie, s: String): Trie = addInner(t, s.toList, "")

def findInner(t: Trie, s: List[Char]): Option[String] = s match {
    case Nil => t.v
    case c::cs => t.m.get(c).flatMap{ t => findInner(t, cs) }
  }

def find(t: Trie, s: String): Option[String] = findInner(t, s.toList)

val root = Trie(None, Map.empty)