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?

It's definitely possible to do this in a type-safe way, without any `Any` or casting—see for example [my answer here](http://stackoverflow.com/a/12648663/334519) for a solution to a similar problem. Your question is a little more complicated, but I'm 100% sure the approach would work. — Travis Brown, Feb 11 '14 at 16:44
My first thought was "maybe Shapeless can handle the general problem of arbitrarily nested Seq to Set?" (https://github.com/milessabin/shapeless) — Randall Schulz, Feb 11 '14 at 17:09
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. — Ed Staub, Feb 11 '14 at 18:08
@RandallSchulz: I can't think of a way Shapeless would make this all that much easier than a Shapeless-less implementation (like [mine below](http://stackoverflow.com/a/21713792/334519)). 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. — Travis Brown, Feb 11 '14 at 22:48

score 8 · Answer 1 · edited May 23 '17 at 11:57

8

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.

edited May 23 '17 at 11:57

Community

1
1

answered Feb 11 '14 at 21:50

Travis Brown

138,631
12
375
680

1

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 :) – James Adam Feb 12 '14 at 11:19
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. – Travis Brown Feb 12 '14 at 12:50
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 – goozez Feb 12 '14 at 16:41
1

@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. – Travis Brown Feb 12 '14 at 17:55
@TravisBrown Is there an error in nsubAmbig2 ? It looks exactly the same as nsubAmbig1. – martin-g Feb 12 '14 at 19:49
@martin-g: No, it's a kind of trick—you make the implicit search fail (for the appropriate types) by providing ambiguous implicits. – Travis Brown Feb 12 '14 at 19:51

James Adam · Accepted Answer · 2014-02-12T00:45:58.963

3

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

edited Feb 12 '14 at 00:45

answered Feb 11 '14 at 15:04

James Adam

2,324
3
16
19

I actually like op's solution much more than this :) – serejja Feb 11 '14 at 15:10
1

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. – James Adam Feb 11 '14 at 15:11
1

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". – Travis Brown Feb 11 '14 at 21:51

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

2 Answers2