Total Collections, rejecting collections of types that do not include all possibilities

Question

Let's say we have the following types:

sealed trait T
case object Goat extends T
case object Monk extends T
case object Tiger extends T

Now, how do you construct a collection of T such that at least one of each sub-T appears in the collection, this constraint being enforced at compile time? A collection where, contrary to this:

val s:Seq[T] = Seq(Goat)

which compiles, this:

val ts:TotalSeq[T] = TotalSeq(Goat, Goat, Tiger)

does not. I've used Scala above, but I would be happy to see solutions in other languages as well.

(Forgive me if my words are a bit off; I have a cold and am amusing myself today with puzzles.)

Answer 1

It looks like the builder pattern with generalized type constraints: http://www.tikalk.com/java/blog/type-safe-builder-scala-using-type-constraints

Something like:

sealed trait TBoolean
sealed trait TTrue extends TBoolean
sealed trait TFalse extends TBoolean

class SeqBuilder[HasGoat <: TBoolean, HasMonk <: TBoolean, HasTiger <: TBoolean] private (seq: Seq[T]) {

  def +=(g: Goat.type) = new SeqBuilder[TTrue, HasMonk, HasTiger](g +: seq)

  def +=(m: Monk.type) = new SeqBuilder[HasGoat, TTrue, HasTiger](m +: seq)

  def +=(t: Tiger.type) = new SeqBuilder[HasGoat, HasMonk, TTrue](t +: seq)

  def build()(implicit evg: HasGoat =:= TTrue, evm: HasMonk =:= TTrue, evt: HasTiger =:= TTrue) = seq
}


object SeqBuilder {
  def apply = new SeqBuilder(Seq())
}

Usage:

scala> SeqBuilder() + Goat + Tiger + Monk build()
res21: Seq[T] = List(Monk, Tiger, Goat)

scala> SeqBuilder() + Goat + Goat + Monk build()
<console>:34: error: Cannot prove that Nothing =:= TTrue.
       SeqBuilder() + Goat + Goat + Monk build()
                                         ^

If the number of instances you want grows you can try using an HMap

Other similar approaches: phantom types: http://james-iry.blogspot.com/2010/10/phantom-types-in-haskell-and-scala.html

Another approach is to ask why you need all 3 objects. Say you want to carry an operation when the seq has all three, then you can do something like:

object SeqBuilder {
  val all = Seq(Goat, Monk, Tiger)

  def apply(t: T*)(onAll: Seq[T] => Unit)(onViolation: => Unit) = {
     val seq = Seq(t:_*)
     if(all forall seq.contains) onAll(seq)
     else onViolation
  }
}

That way, the function onAll is not called if not all required Ts have been supplied and otherwise the violation function is called