How to make a nested toSet in scala in an idiomatic way?

Question

Is there a more idiomatic way to change a nested sequence of sequences into a nested set of sets?

def toNestedSet[T](tsss: Seq[Seq[Seq[T]]]): Set[Set[Set[T]]]  = 
   tsss.map(_.map(_.toSet).toSet).toSet

Is it possible to implement a function which would work with lists of any depth?

Dentoid

It's definitely possible to do this in a type-safe way, without any Any or casting—see for example my answer here for a solution to a similar problem. Your question is a little more complicated, but I'm 100% sure the approach would work. – Boutique

My first thought was "maybe Shapeless can handle the general problem of arbitrarily nested Seq to Set?" (github.com/milessabin/shapeless) – Brokenhearted

When I find myself in this situation, I usually make a type definition for one or more inner nesting(s) that I need to reuse a lot anyway. – Wyatan

@RandallSchulz: I can't think of a way Shapeless would make this all that much easier than a Shapeless-less implementation (like mine below). Maybe I'm wrong, though—e.g. there may be some way to get SYB to do this that I'm not seeing at the moment. – Boutique

Answer 1

To address the second part of your question (processing a list of arbitrary depth), something like this would work (type erasure gets in the way a bit):

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

Note: quick and dirty -- it works, but fairly easy to break :)

Edit: The cast was redundant

Decoct

I actually like op's solution much more than this :) – Contrarious

Op's solution doesn't work with a Seq of arbitrary depth. If the depth is known, then yes - that's the way to go. – Decoct

I wouldn't say type erasure "gets in the way" so much as "type erasure makes dispatching on type in a pattern match almost as unpleasant as it ought to be". – Boutique

Answer 2

This actually isn't too bad at all (see my answer here to a similar question for some additional discussion of this approach):

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)

And then:

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

Statically typed as a Set[Set[Set[Set[[Int]]]] and all.

Well, I lied a little bit. The <:!< above isn't actually in the standard library. It is in Shapeless, though, or you can very, very easily define it yourself:

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

And that's really all.

Boutique

Well, that's clever. I have a problem at work involving a more complicated recursive data structure than the OP which I currently process using a more complex variation of my answer below (and I was never really happy with). I might try to adapt this :) – Decoct

One footnote: I'm ignoring variance issues here for the sake of clarity, which means this version will only work if your sequences are statically typed as Seq. It wouldn't be hard to "fix" this—just a little messier. – Boutique

Hi, I like both answers, but the one provided by James Adam solves the problem and remains simple. That is why I accepted his answer. Yet still your answer might be more convenient for advanced applications and users. +1 – Dentoid

@goozez: Fair enough, but I'll just point out that losing the type information means you'll have to cast the result, which eliminates much of the advantage of having an implementation of this for arbitrary nestings right off the bat. – Boutique

@TravisBrown Is there an error in nsubAmbig2 ? It looks exactly the same as nsubAmbig1. – Tbar

@martin-g: No, it's a kind of trick—you make the implicit search fail (for the appropriate types) by providing ambiguous implicits. – Boutique