Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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

like image 700
troutwine Avatar asked Jun 02 '11 15:06

troutwine


1 Answers

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

like image 140
IttayD Avatar answered Oct 10 '22 03:10

IttayD