Cómo implementar un conjunto con una igualdad definida por el usuario

Question

Esta pregunta está relacionada con this one: ¿es posible crear una clase Set-like (lo que significa que extiende el rasgo Set) en Scala donde se usa la igualdad para definir la contención relación es definida por el usuario en lugar de ser ==?

Una forma de comprobar si realmente funciona es comprobar si filter devuelve el mismo tipo de colección.

// typeclass for equality 
trait Equals[T] { 
    def isEqual(t1: T, t2: T): Boolean 
} 

// an object representing plane coordinates 
case class Coordinate(i: Int, j: Int) 

// an equality saying that 2 coordinates are equal if they are on 
// the same horizontal line 
implicit def horizontalEquality: Equals[Coordinate] = new Equals[Coordinate] { 
    def isEqual(t1: Coordinate, t2: Coordinate) = t1.i == t2.i 
} 

// we create an EqualitySet[T] where T must verify [T : Equals]  
val set = EqualitySet[Coordinate]() 

// set2 must be of type EqualitySet[Coordinate] 
val set2 = set.filter(_.i > 0) 

Answer 1

Creamos esta solución como grupo en un entrenamiento de Scala con Miles Sabin (@milessabin).

import scala.collection.mutable.ListBuffer 
import scala.collection.generic.CanBuildFrom 
import scala.collection.SetLike 
import scala.collection.mutable.Builder 

/** 
* we extend Set[T] to provide the Set-like interface 
* we extends SetLike[T, EqualitySet[T]] to specify that Set methods will return 
* instances of type EqualitySet (and not simply Set) 
*/ 
trait EqualitySet[T] extends Set[T] with SetLike[T, EqualitySet[T]] { outer => 
    /** we need to provide an Equals[T] instance to create an EqualitySet[T] */ 
    implicit def equality: Equals[T] 

    /** our internal implementation as a list of elements */ 
    protected val set = ListBuffer[T]() 

    /** we need to implements those 4 methods */ 
    def contains(t: T) = set.exists(equality.isEqual(_, t)) 
    def +(t: T) = { if (!contains(t)) set += t; this } 
    def -(t: T) = { set -= t; this } 
    def iterator = set.iterator 

    /** we must be able to provide an empty set with the proper equality definition */ 
    override def empty = new EqualitySet[T] { 
    override def equality = outer.equality 
    } 
} 

/** 
* Companion object for the EqualitySet class 
*/ 
object EqualitySet { 

    /** 
    * this implicit is absolutely necessary to be able to preserve the resulting 
    * collection type when calling `filter` 
    */ 
    implicit def canBuildFrom[T] = new CanBuildFrom[EqualitySet[T], T, EqualitySet[T]] { 
    def apply(from: EqualitySet[T]): Builder[T, EqualitySet[T]] = 
     new Builder[T, EqualitySet[T]] { 
     // use a ListBuffer internally to accumulate elements 
     private val elems = ListBuffer[T]() 
     def +=(t: T) = { 
      if (!elems.exists(from.equality.isEqual(_, t))) elems += t 
      this 
     } 
     def clear() = elems.clear 

     // when we finish building the collection 
     // we can return an EqualitySet with the original equality relation 
     def result() = new EqualitySet[T] { 
      override val set = elems 
      override def equality = from.equality 
     } 
    } 
    def apply(): Builder[T, EqualitySet[T]] = 
     sys.error("this can't be implemented, because no equality instance is provided") 
    } 

    /** @return an EqualitySet for a type T having an Equals instance */ 
    def apply[T : Equals](ts: T*) = { 
    var set = new EqualitySet[T] { 
     def equality = implicitly[Equals[T]] 
    }.empty 
    ts.foreach { t => set += t } 
    set 
    } 
} 

Entonces, cuando usamos el código anterior se obtiene:

scala> val set = EqualitySet[Coordinate](Coordinate(-1, 2), 
             Coordinate(-1, 3), 
             Coordinate(1, 4)) 

set: java.lang.Object with test.EqualitySet[Coordinate] = 
    Set(Coordinate(-1,2) 
     Coordinate(1,4)) 

scala> val set2 = set.filter(_.i > 0) 

// still an EqualitySet[Coordinate] \o/ */ 
set2: test.EqualitySet[Coordinate] = Set(Coordinate(1,4))