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 '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

1 Answer 1

  1. 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.

  2. 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 < 0 => 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 < 0 => 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.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.