Как сделать вложенный toSet в scala идиоматическим способом?

Чтобы ответить на вторую часть вашего вопроса (обработка списка произвольной глубины), сработает что-то вроде этого (стирание типа немного мешает):

  def toNestedSet(ts: Seq[Any]): Set[Any] = {
    ts.foldLeft[Set[Any]](Set())((acc, b) => b match {
        case s: Seq[_] => acc + toNestedSet(s)
        case x => acc + x
    })
  } 

Примечание: быстро и грязно - это работает, но довольно легко сломать :)

Редактировать: актёрский состав был излишним

На самом деле это совсем не так уж плохо (см. мой ответ здесь на аналогичный вопрос для дополнительного обсуждения этого подхода) :

trait Setsifier[I, O] { def apply(i: I): O }

object Setsifier {
  def apply[I, O](f: I => O) = new Setsifier[I, O] { def apply(i: I) = f(i) }

  implicit def base[I](implicit ev: I <:!< Seq[_]) = apply((_: Seq[I]).toSet)

  implicit def rec[I, O](implicit s: Setsifier[I, O]) =
    apply((_: Seq[I]).map(s(_)).toSet)
}

def setsify[I, O](i: I)(implicit s: Setsifier[I, O]) = s(i)

А потом:

scala> println(setsify(Seq(Seq(Seq(Seq(1)), Seq(Seq(2, 3))))))
Set(Set(Set(Set(1)), Set(Set(2, 3))))

Статически типизирован как Set[Set[Set[Set[[Int]]]] и все.

Ну, я немного солгал. <:!< выше на самом деле нет в стандартной библиотеке. Однако он находится в Shapeless, или вы можете очень и очень легко определить его самостоятельно:

trait <:!<[A, B]

implicit def nsub[A, B] : A <:!< B = new <:!<[A, B] {}
implicit def nsubAmbig1[A, B >: A] : A <:!< B = sys.error("Don't call this!")
implicit def nsubAmbig2[A, B >: A] : A <:!< B = sys.error("Don't call this!")

И это действительно все.