Implementing a generic and covariant Set in Scala

I'm struggling with manually implementing a simple purely functional Set that's also generic and covariant on its type parameter:

• Set must be a trait, allowing for multiple implementations.

• it must be covariant on the type of the element it contains.

• an implementation's type must not be lost when calling methods that return a new Set.

The first two points are fairly trivial and simply mean that the trait should look something like:

trait Set[+A] {
  def isEmpty: Boolean
  def insert[B >: A](b: B)(implicit order: Ordering[B]): Set[B]
  def contains[B >: A](b: B)(implicit order: Ordering[B]): Boolean
}

The problem with this implementation is that insert, for example, will always return an instance of Set. If I were to write a specialised implementation of Set with useful helper methods, its type would be lost as soon as an element was inserted in it.

This is what I've come up with, which seems to work but I still find confusing and can't help but feel is over-complicated (recursive higher kinded types!):

trait Set[+A, Repr[+X] 

  def isEmpty: Boolean
  def insert[B >: A](b: B)(implicit order: Ordering[B]): Repr[B]
  def contains[B >: A](b: B)(implicit order: Ordering[B]): Boolean
}

Here's a sample implementation using a simple binary tree:

```
sealed trait CustomSet[+A] extends Set[A, CustomSet]

case class NodeA extends CustomSet[A] {
override def isEmpty = false

override def insertB >: A(implicit order: Ordering[B]) =
if(order.lt(b, value)) Node(value, left.insert(b), right)
else if(order.gt(b, value)) Node(value, left, right.insert(b))
else this

override def containsB >: A(implicit order: Ordering[B]) =
if(order.lt(b, value)) left.contains(b)
else if(order.gt(b, value)) right.contains(b)
else true
}

case object Leaf extends CustomSet[Nothing] {
override def isEmpt

-
The this: Repr[A] is not absolutely necessary, but it you omit it, you're encoding a sort of weird type constraint:
that the class is not necessarily a Repr, but its insert[B] must produce a Repr[B] (who's insert[C] produces a Repr[C], and so on).
I can't think of a realistic situation where having or not having the self-type would prevent or lead to a bug, so IMO it doesn't actually matter much.

-
Your recursive higher-kinded type signature is absolutely fine, and in fact very closely mirrors that of SetLike from the standard collection library.

There is at least one alternative: making it a typeclass. Here's what it might look like:

trait CovariantSet[S[+_]] {
  def isEmpty[A](xs: S[A]): Boolean
  def contains[A, B >: A](b: B)(xs: S[A])(implicit order: Ordering[B]): Boolean
  def insert[A, B >: A](b: B)(xs: S[A])(implicit order: Ordering[B]): S[B]
}

sealed trait CustomSet[+A]
case object Leaf extends CustomSet[Nothing]
case class Node[+A](value: A, left: CustomSet[A], right: CustomSet[A]) extends CustomSet[A]

object CustomSet {
  implicit val customSetIsCovariantSet: CovariantSet[CustomSet] = new CovariantSet[CustomSet] {
    override def isEmpty[A](xs: CustomSet[A]): Boolean = xs == Leaf

    override def insert[A, B >: A](b: B)
                                  (xs: CustomSet[A])
                                  (implicit order: Ordering[B]): CustomSet[B] = xs match {
      case Leaf => Node(b, Leaf, Leaf)
      case Node(v, l, r) => order.compare(b, v) match {
        case 0 => xs
        case i if i  Node(v, insert(b)(l), r)
        case _ => Node(v, l, insert(b)(r))
      }
    }

    @tailrec
    override def contains[A, B >: A](b: B)
                                    (xs: CustomSet[A])
                                    (implicit order: Ordering[B]): Boolean = xs match {
      case Leaf => false
      case Node(v, l, r) => order.compare(b, v) match {
        case 0 => true
        case i if i  contains(b)(l)
        case _ => contains(b)(r)
      }
    }
  }
}

The idea is that the data structure (the CustomSet) can be defined separately from the evidence that it has an instance for the CovariantSet typeclass (customSetIsCovariantSet). Whether or not you think it's simpler is a matter of opinion, but it does at least avoid the recursive type.

You can then enrich CovariantSets for convenience:

object CovariantSet {
  implicit class Ops[S[+_], A](xs: S[A])(implicit ev: CovariantSet[S]) {
    def isEmpty: Boolean = ev.isEmpty(xs)
    def contains[B >: A](b: B)(implicit order: Ordering[B]): Boolean = ev.contains(b)(xs)
    def insert[B >: A](b: B)(implicit order: Ordering[B]): S[B] = ev.insert(b)(xs)
  }
}

I would also probably make the Node constructor private, so users can't construct a malformed (out of order) tree.

Your larger and more fundamental design problem is that the data structure doesn't make sense unless the Ordering is fixed (or at least its compare operation doesn't change its mind about values already in the Set).

Here are a couple problematic examples of where this can go wrong:

Leaf.insert(1).insert(2).contains(2) // true. great, working as expected

Leaf.insert(1).insert(2).contains(2)(Ordering.Int.reverse) // false. your data structure is broken

Leaf.insert(1).insert(2)(Ordering.Int.reverse).contains(2) // false. your data structure is broken

There are a couple ways around this I can think of, the first more practical than the second:

-
Implement a covariant HashSet instead. Every object in Scala has a hashCode: Int and an equals(other: Any): Boolean method, which is all you need.

-
Store an Ordering[A] in the Set. Whenever you implicitly pass in a new Ordering[B], also implicitly pass in an object that proves that the new Ordering[B] agrees with every decision the old Ordering[A] has already made.

StackExchange Code Review Q#58365, answer score: 3