Prefix Trie

                b                s                 t
                y*            e     h              h
                            a* l    e*             e*
                               l    l
                               s*   l
                                    s*
                                    
* denotes the node at which an entry terminates

We can express it with a single member AST backed by a recursive Map . Boolean , when true , denotes that the sequence traversed so far demarcates an entry in the trie

case class PrefixTrie[A](repr: Map[A, (Boolean, PrefixTrie[A])])

object PrefixTrie {

  def find[A](l: List[A], t: PrefixTrie[A]): Boolean =
    l match {
      case Nil => true
      case a :: as =>
        t.repr
          .get(a)
          .fold(false) { case (_, next) => find(as, next) }
    }

  def insert[A](l: List[A], t: PrefixTrie[A]): PrefixTrie[A] =
    l match {
      case Nil      => t
      case a :: Nil => PrefixTrie(Map(a -> (true -> t)))
      case a :: as =>
        t.repr
          .get(a)
          .fold(
            PrefixTrie[A](
              t.repr + (a -> (false -> insert(as, PrefixTrie(Map.empty)))))
          ) {
            case (stop, next) =>
              PrefixTrie[A](t.repr + (a -> (stop -> insert(as, next))))
          }

    }

}

Although this isn't the "perfect" type. A more complete type is:

import cats.data.NonEmptyMap

case class PrefixTrie[A](
      repr: Option[NonEmptyMap[A, (Boolean, PrefixTrie[A])]])

However programming against this AST complicates the code further and involves a bit of a hack, though this is only because we're using cats.data.NonEmptyMap which is implemented in terms of scala.collection.immutable.SortedMap You could avoid this by defining your own thin wrapper around Map that forces construction via def apply(head: (K, V), tail: (K, V)*): NonEmptyMap[K, V]

import cats.Order

object PrefixTrie {

  /** because NonEmptyMap is backed by SortedMap this is a hack to just
   *  maintain insertion order */
  implicit def ordering[A]: Ordering[A] = new Ordering[A] {
      override def compare(x: A, y: A): Int = 1
    }
  implicit def order[A]: Order[A] = new Order[A] {
    override def compare(x: A, y: A): Int = 1
  }

  def find[A](l: List[A], t: PrefixTrie[A]): Boolean =
    (l, t.repr) match {
      case (Nil, _)  => true
      case (_, None) => false
      case (a :: as, Some(m)) =>
        m(a)
          .fold(false) { case (_, next) => find(as, next) }
    }

  def insert[A: Ordering: Order](
    l: List[A],
    t: PrefixTrie[A]): PrefixTrie[A] =
    (l, t.repr) match {
      case (Nil, _) => t
      case (a :: Nil, _) =>
        PrefixTrie(
          Some(
            NonEmptyMap(
              a -> (true -> t),
              SortedMap.empty[A, (Boolean, PrefixTrie[A])])))
      case (a :: as, mOpt) =>
        mOpt.fold(
          PrefixTrie[A](
            Some(
              NonEmptyMap(
                a -> (false -> insert(as, PrefixTrie(None))),
                SortedMap.empty[A, (Boolean, PrefixTrie[A])]
              )
            )
          )
        )(
          m =>
            m(a)
              .fold(
                PrefixTrie[A](
                  Some(m.add(a -> (false -> insert(as, PrefixTrie(None))))))
              ) {
                case (stop, next) =>
                  PrefixTrie[A](
                    Some(m.add(a -> (stop -> insert(as, next)))))
            }
        )

    }

}