Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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?
share|improve this question

migrated from programmers.stackexchange.com Jul 29 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 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 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 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 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 at 9:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.