Всего коллекций, отклоняя коллекции типов, которые не включают все возможности

Question

Допустим, у нас есть следующие типы:

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

Теперь, как вы создаете коллекцию из T таким образом, чтобы по крайней мере один каждого подпункта T появлялся в коллекции, это ограничение было применено во время компиляции? Коллекция, в которой вопреки этому:

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

, который компилируется, это:

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

нет. Я использовал Scala выше, но я был бы рад видеть решения и на других языках.

(Простите, если мои слова немного не в порядке; у меня простуда и я сегодня забавляюсь головоломками.)

Answer 1

Это похоже на шаблон построителя с обобщенными типовыми ограничениями: http://www.tikalk.com/java/blog/type-safe-builder-scala-using-type-constraints

Что-то вроде:

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

Использование:

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()
                                         ^

Если количество нужных вам экземпляров растет, вы можете попробовать использовать HMap

Другие похожие подходы: фантомные типы: http://james -iry.blogspot.com / 2010/10 / phantom-types-in-haskell-and-scala.html

Другой подход - спросить, зачем вам все 3 объекта. Скажем, вы хотите выполнить операцию, когда в seq есть все три, тогда вы можете сделать что-то вроде:

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

Таким образом, функция onAll не вызывается, если предоставлены не все требуемые значения Ts, а в противном случае вызывается функция нарушения

Answer 2

Если я правильно интерпретирую это ...

{-# 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)

Имейте в виду, что не предпринимались попытки сделать это годным к употреблению . Это невероятно неуклюже.

Теперь, учитывая эти значения:

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

y = TG TGoat TNil

И эта функция:

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

... тогда только f x будет печатать проверку, а не f y.

N.B. Удаление элементов из последовательности оставлено читателю в качестве упражнения.

---

РЕДАКТИРОВАТЬ : После дальнейшего рассмотрения я решил, что вышеупомянутое не достаточно ужасно. Вот:

Какой-то таинственно знакомый шаблон:

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

Немного общего взлома:

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

Ааааааа и выплата:

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

Как и выше, f2 x2 проверки типов, в то время как f2 y2 не удается.

Это все еще грязно и довольно болезненно, но гораздо более универсально!

И просто чтобы доказать, что результат все еще может обрабатываться как обычный тип данных в других обстоятельствах, вот пример 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]

Так что теперь мы можем делать такие вещи, как show только последовательности, которые содержат все три вида предметов:

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

Answer 3

Вы не можете сделать это с точно синтаксисом, который вы предложили, но вы можете приблизиться;единственный компромисс, который вы должны сделать, это использовать оператор вместо ,.Я выбрал ~, и поскольку вы не указали точное поведение при типе , а не , указанном слева, я сделал что-то неопределенно разумное.это головная боль, однако.Хаскелл лучше выражает это кратко;стратегия похожа на ту, что уже предоставил camccann.

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

Давайте посмотрим, как мы можем использовать это:

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

Answer 4

Я сократил его до двух подклассов, чтобы сделать его понятнее и короче, но этот принцип можно применять к любому числу подклассов. К сожалению, для многих подклассов он становится довольно длинным.

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
  }

}