Implementing a generic and covariant Set in Scala
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 &gt;: A](b: B)(xs: S[A])(implicit order: Ordering[B]): Boolean
  def insert[A, B &gt;: 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 &gt;: A](b: B)
                                  (xs: CustomSet[A])
                                  (implicit order: Ordering[B]): CustomSet[B] = xs match {
      case Leaf =&gt; Node(b, Leaf, Leaf)
      case Node(v, l, r) =&gt; order.compare(b, v) match {
        case 0 =&gt; xs
        case i if i &lt; 0 =&gt; Node(v, insert(b)(l), r)
        case _ =&gt; Node(v, l, insert(b)(r))
      }
    }

    @tailrec
    override def contains[A, B &gt;: A](b: B)
                                    (xs: CustomSet[A])
                                    (implicit order: Ordering[B]): Boolean = xs match {
      case Leaf =&gt; false
      case Node(v, l, r) =&gt; order.compare(b, v) match {
        case 0 =&gt; true
        case i if i &lt; 0 =&gt; contains(b)(l)
        case _ =&gt; 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 &gt;: A](b: B)(implicit order: Ordering[B]): Boolean = ev.contains(b)(xs)
    def insert[B &gt;: 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.