集合不包含一個地方a⊆b和b是集合中

Question

我需要無視包含在其他元素的集合：

Picky(Set(1, 2)) + Set(1) should equal(Picky(Set(1, 2))) 

Picky(Set(1)) + Set(1, 2) should equal(Picky(Set(1, 2))) 

Picky(Set(1, 3)) + Set(1, 2) should equal(Picky(Set(1, 3), Set(1, 2))) 

Picky(Set(1, 2), (Set(1))) should equal(Picky(Set(1, 2))) 

其實我有一個解決方案

case class Picky[T] private(sets: Set[Set[T]]) { 
    def +(s: Set[T]): Picky[T] = Picky(Picky.internalAddition(this.sets, s)) 
} 

object Picky { 
    def apply[T](sets: Set[T]*): Picky[T] = 
    Picky((Set[Set[T]]() /: sets)(internalAddition(_, _))) 

    private def internalAddition[T](c: Set[Set[T]], s: Set[T]): Set[Set[T]] = 
    if (c.exists(s subsetOf _)) c else c.filterNot(_ subsetOf s) + s 
} 

但是我想知道是否已經有一個包含這個概念的集合，因爲我試圖做的聽起來有點像一個具有一種還原函數的集合，就像下面一個接受worse函數的虛構集合（在我們的具體實現中爲情況）：

PickySet(){(a, b) => a subset b} 

如爲任何的元件（A，B）如果worse(a, b)返回true，a將被丟棄

爲了明確與集的差異，一組將是PickySet的一種特殊情況：

PickySet(){_ == _} 

Answer 1

我不認爲你會找到一個方便的現成的實現這個集合，但你可以讓你更通用一點，通過使用scala.math.PartialOrdering和事實，集是部分排序的事實子集關係。

首先用於定義Picky。實際上，你想要的只是一個容器，只能容納maximal elements，其中沒有元素相對於對方排序，並且所有較小的元素都已被刪除。

class Picky[A: PartialOrdering] private(val xs: Seq[A]) { 
    def +(y: A): Picky[A] = new Picky(Picky.add(xs, y)) 
    override def toString = "Picky(%s)".format(xs.mkString(", ")) 
} 

object Picky { 
    def apply[A: PartialOrdering](xs: A*): Picky[A] = 
    new Picky(xs.foldLeft(Seq.empty[A])(add)) 

    private def add[A](xs: Seq[A], y: A)(implicit ord: PartialOrdering[A]) = { 
    val notSmaller = xs.filterNot(ord.lteq(_, y)) 
    if (notSmaller.exists(ord.lteq(y, _))) notSmaller else notSmaller :+ y 
    } 
} 

接着用於套部分排序，這是僅定義如果所述集合中的一個是另一個的子集（可能是平凡）：

implicit def subsetOrdering[A] = new PartialOrdering[Set[A]] { 
    def tryCompare(x: Set[A], y: Set[A]) = 
    if (x == y) Some(0) 
    else if (x subsetOf y) Some(-1) 
    else if (y subsetOf x) Some(1) 
    else None 

    def lteq(x: Set[A], y: Set[A]) = 
    this.tryCompare(x, y).map(_ <= 0).getOrElse(false) 
} 

的tryCompare以下等效定義可以想見快一點：

def tryCompare(x: Set[A], y: Set[A]) = { 
    val s = (x & y).size 
    if (s == x.size || s == y.size) Some(x.size - y.size) else None 
} 

現在我們得到想要的結果：

scala> Picky(Set(1, 2)) + Set(1) 
res0: Picky[scala.collection.immutable.Set[Int]] = Picky(Set(1, 2)) 

scala> Picky(Set(1)) + Set(1, 2) 
res1: Picky[scala.collection.immutable.Set[Int]] = Picky(Set(1, 2)) 

scala> Picky(Set(1, 3)) + Set(1, 2) 
res2: Picky[scala.collection.immutable.Set[Int]] = Picky(Set(1, 3), Set(1, 2)) 

scala> Picky(Set(1, 2), (Set(1))) 
res3: Picky[scala.collection.immutable.Set[Int]] = Picky(Set(1, 2)) 

請注意，我們可以很容易地定義一個替代的偏序排列，它將給出Picky普通舊集合語義（即只有相等的東西相對於彼此排序，並且它們總是相等的）。