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 t开发者_运维百科hat 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.)

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

If I'm interpreting this correctly...

{-# LANGUAGE GADTs #-}
{-# LANGUAGE EmptyDataDecls #-}

data Goat
data Monk
data Tiger

data T a where
    TGoat  :: T Goat
    TMonk  :: T Monk
    TTiger :: T Tiger

data TSeq a where
    TNil :: TSeq ((), (), ())
    TG   :: T Goat -> TSeq ((), m, t) -> TSeq (Goat, m, t)
    TM   :: T Monk -> TSeq (g, (), t) -> TSeq (g, Monk, t)
    TT   :: T Tiger -> TSeq (g, m, ()) -> TSeq (g, m, Tiger)
    TCG  :: T Goat -> TSeq (Goat, m, t) -> TSeq (Goat, m, t)
    TCM  :: T Monk -> TSeq (g, Monk, t) -> TSeq (g, Monk, t)
    TCT  :: T Tiger -> TSeq (g, m, Tiger) -> TSeq (g, m, Tiger)

Be aware that no attempt has been made to make this usable. It's incredibly clumsy.

Now, given these values:

x = TCG TGoat (TG TGoat (TT TTiger (TM TMonk TNil)))

y = TG TGoat TNil

And this function:

f :: TSeq (Goat, Monk, Tiger) -> a
f _ = undefined

...then only f x will type check, not f y.

N.B. Removing items from the sequence is left as an exercise for the reader.

EDIT: Upon further consideration I've decided the above is not at all terrible enough. Behold:

Some mysteriously familiar boilerplate:

data Yes = Yes
data No = No

class TypeEq' () x y b => TypeEq x y b | x y -> b
instance TypeEq' () x y b => TypeEq x y b

class TypeEq' q x y b | q x y -> b
class TypeEq'' q x y b | q x y -> b


instance TypeCast b Yes => TypeEq' () x x b
instance TypeEq'' q x y b => TypeEq' q x y b
instance TypeEq'' () x y No

class TypeCast   a b   | a -> b, b->a   where typeCast   :: a -> b
class TypeCast'  t a b | t a -> b, t b -> a where typeCast'  :: t->a->b
class TypeCast'' t a b | t a -> b, t b -> a where typeCast'' :: t->a->b
instance TypeCast'  () a b => TypeCast a b where typeCast x = typeCast' () x
instance TypeCast'' t a b => TypeCast' t a b where typeCast' = typeCast''
instance TypeCast'' () a a where typeCast'' _ x  = x

A bit of general hackery:

infixr 1 :*:
data NIL
data h :*: t = h :*: t

class TIns x ys r | x ys -> r
instance TIns x NIL (x :*: NIL)
instance ( TypeEq x h b 
         , TIns' b x h t r
         ) => TIns x (h :*: t) r


class TIns' b x h t r | b x h t -> r
instance TIns' Yes x h t (h :*: r)
instance (TIns x t r) => TIns' No x h t (h :*: r)


class TElem x ys r | x ys -> r
instance TElem x NIL No
instance (TypeEq x h b, TElem' b x h t r) => TElem x (h :*: t) r

class TElem' b x h t r | b x h t -> r
instance TElem' Yes x h t Yes
instance (TElem x t r) => TElem' No x h t r

Aaaaaaaand the payoff:

data TSeq2 a b where
    TNil2  :: TSeq2 NIL NIL
    TCons2 :: (TIns x ys r) => T x -> TSeq2 xs ys -> TSeq2 (x :*: xs) r

class (TElem x ys Yes) => Has ys x
instance (TElem x ys Yes) => Has ys x

class HasAll ys xs
instance HasAll ys NIL
instance (ys `Has` h, ys `HasAll` t) => HasAll ys (h :*: t)

x2 = TCons2 TGoat (TCons2 TGoat (TCons2 TTiger (TCons2 TMonk TNil2)))

y2 = TCons2 TGoat TNil2

f2 :: (s `HasAll` (Goat :*: Tiger :*: Monk :*: NIL)) => TSeq2 q s -> a
f2 _ = undefined

As with the above, f2 x2 typechecks, while f2 y2 fails.

This is still messy and rather painful to use, but far more generic!

And just to prove that the result can still be treated as an ordinary data type in other circumstances, here's an instance of Show:

instance Show (T a) where
    show TGoat = "TGoat"
    show TMonk = "TMonk"
    show TTiger = "TTiger"

instance Show (TSeq2 a b) where
    show TNil2 = "[]"
    show (TCons2 x xs) = concat [show x, ":", show xs]

So now we can do things like show only sequences that contain all three kinds of item:

showTotal :: (s `HasAll` (Goat :*: Tiger :*: Monk :*: NIL)) => TSeq2 q s -> String
showTotal = show

You can't do it with exactly the syntax you've proposed, but you can get close; the only compromise you have to make is using an operator instead of ,. I've chosen ~, and since you didn't exactly specify the behavior when the type is not specified on the left, I've made something vaguely sensible.

The code is a headache, however. Haskell is better at concisely expressing this; the strategy is similar to what camccann has already provided.

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

  implicit def Gx(g: Goat.type) = new Goats(Seq(g))
  implicit def Mx(m: Monk.type) = new Monks(Seq(m))
  implicit def Tx(t: Tiger.type) = new Tigers(Seq(t))

  trait Combo { def s: Seq[T] }

  case class Goats(s: Seq[T]) extends Combo {
    def ~(g: Goat.type) = Goats(s :+ g)
    def ~(m: Monk.type) = GoatMonk(s :+ m)
    def ~(t: Tiger.type) = GoatTiger(s :+ t)
  }
  case class Monks(s: Seq[T]) extends Combo {
    def ~(g: Goat.type) = GoatMonk(s :+ g)
    def ~(m: Monk.type) = Monks(s :+ m)
    def ~(t: Tiger.type) = MonkTiger(s :+ t)
  }
  case class Tigers(s: Seq[T]) extends Combo {
    def ~(g: Goat.type) = GoatTiger(s :+ g)
    def ~(m: Monk.type) = MonkTiger(s :+ m)
    def ~(t: Tiger.type) = Tigers(s :+ t)
  }

  case class GoatMonk(s: Seq[T]) extends Combo {
    def ~(g: Goat.type) = GoatMonk(s :+ g)
    def ~(m: Monk.type) = GoatMonk(s :+ m)
    def ~(t: Tiger.type) = GoatMonkTiger(s :+ t)
  }
  case class GoatTiger(s: Seq[T]) extends Combo {
    def ~(g: Goat.type) = GoatTiger(s :+ g)
    def ~(m: Monk.type) = GoatMonkTiger(s :+ m)
    def ~(t: Tiger.type) = GoatTiger(s :+ t)
  }
  case class MonkTiger(s: Seq[T]) extends Combo {
    def ~(g: Goat.type) = GoatMonkTiger(s :+ g)
    def ~(m: Monk.type) = MonkTiger(s :+ m)
    def ~(t: Tiger.type) = MonkTiger(s :+ t)
  }

  case class GoatMonkTiger(s: Seq[T]) {
    def ~(t: T) = GoatMonkTiger(s :+ t)
  }

  class TotalSeq[A](val seq: Seq[A]) {}
  implicit def total_to_regular[A](ts: TotalSeq[A]) = ts.seq
  object TotalSeq {
    def apply(t: T) = Seq(t)
    def apply(co: Combo) = co.s
    def apply(gmt: GoatMonkTiger) = new TotalSeq(gmt.s)
  }
}

Let's see how we can use this:

scala> import Example._
import Example._

scala> val mmm = TotalSeq(Monk ~ Monk ~ Monk)
mmm: Seq[Example.T] = List(Monk, Monk, Monk)

scala> val mmm2: Seq[T] = TotalSeq(Monk ~ Monk ~ Monk)
mmm2: Seq[Example.T] = List(Monk, Monk, Monk)

scala> val mmm3: TotalSeq[T] = TotalSeq(Monk ~ Monk ~ Monk)
<console>:11: error: type mismatch;
 found   : Example.Monks
 required: Example.GoatMonkTiger
       val mmm3: TotalSeq[T] = TotalSeq(Monk ~ Monk ~ Monk)
                                                    ^

scala> TotalSeq(Tiger ~ Goat ~ Goat ~ Goat)
res5: Seq[Example.T] = List(Tiger, Goat, Goat, Goat)

scala> TotalSeq(Goat ~ Goat ~ Tiger ~ Monk)
res6: Example.TotalSeq[Example.T] = Example$TotalSeq@5568db68

scala> val gmt: TotalSeq[T] = TotalSeq(Goat ~ Goat ~ Tiger ~ Monk)
gmt: Example.TotalSeq[Example.T] = Example$TotalSeq@f312369

I have reduced it to two subclasses to make it clearer and shorter, but the principle can be applied to any number of subclasses. Unfortunately though, it gets quite long for many subclasses.

sealed trait T
case class Monk extends T
case class Tiger extends T

class BaseList(val head:T, val tail:BaseList) {
  def ::(m:Monk) = new BaseList(m, this) with ListWithMonk
  def ::(t:Tiger) = new BaseList(t, this) with ListWithTiger

}
object Empty extends BaseList(null, null)

trait ListWithMonk extends BaseList {
  self:BaseList =>
  override def ::(t:Tiger) = new BaseList(t, self) with ListWithBoth
}
trait ListWithTiger extends BaseList {
  self:BaseList =>
  override def ::(m:Monk) = new BaseList(m, self) with ListWithBoth
}

trait ListWithBoth extends ListWithMonk with ListWithTiger

object Main {
  def main(args:Array[String]) {
    val l:ListWithBoth = new Monk :: new Tiger :: Empty
    val l2:ListWithBoth = new Tiger :: new Monk :: Empty
    // does not compile: val l3:ListWithBoth = new Tiger :: new Tiger :: Empty
  }

}