# 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] <: Set[X, Repr]] {
this: Repr[A] =>

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 Node[A](value: A, left: CustomSet[A], right: CustomSet[A]) extends CustomSet[A] {
override def isEmpty = false

override def insert[B >: A](b: B)(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 contains[B >: A](b: B)(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 isEmpty                                        = true
override def insert[B](b: B)(implicit order: Ordering[B])   = Node(b, Leaf, Leaf)
override def contains[B](b: B)(implicit order: Ordering[B]) = false
}


The questions that I have are:

• I don't believe the self-type is strictly necessary here. Are there good reasons to leave it? to remove it?
• is this the correct / best / simplest way to implement what I'm trying to write? Are there any alternatives?
-

## migrated from programmers.stackexchange.comJul 29 '14 at 10:04

This question came from our site for professional programmers interested in conceptual questions about software development.

It might help to add the name of the programming language you're using to the question somewhere if it isn't a C-style language. I'm sure whoever sees this will know based on the syntax what you're talking about, but there's no reason for us to click on this if we don't use this language. –  Trixie Wolf Jul 28 '14 at 20:30
My apologies - I tagged the question as Scala, but that's obviously less clear than I thought. I changed the question's title to be more precise. –  Nicolas Rinaudo Jul 28 '14 at 20:33
Thank you! (I'm kind of a n00b here so the tag might be sufficient for most members--if that is the case I apologize for the request.) –  Trixie Wolf Jul 28 '14 at 20:34
Ah, crap, not half the noob I am apparently. I meant to post that in codereview, where it makes much more sense. Any kind soul around with enough privilege to do so? –  Nicolas Rinaudo Jul 29 '14 at 7:20
why do you want your set to be covariant? To me a contravariant Set makes a lot more sense. –  Martijn Oct 23 '14 at 9:52