Existential types in Scala

Question

Please find below a short example which puzzles me.

I must concede that I have some difficulties to manipulate existential types in Scala.

How should I solve the type mismatch line 56 ? proposer is OK type _$1 while proposers is of type _$1 <: Individual

Thanks in advance,

Maxime.

class Individual(n: String) {
  protected val name=n
  var preferred: Individual = this
  override def toString(): String=name
}

class Man(n: String) extends Individual(n) { }

class Woman(n: String) extends Individual(n) { }

class Marriage(m: Man, w: Woman){
  private val man=m
  private val woman=w
  def this(w: Woman, m: Man) = this(m,w)
  override def toString(): String = man+"--"+woman
}

class Matching(){
  private var list: List[Marriage] = Nil
  def add(m: Marriage): Unit = { list = m ::list }
  override def toString(): String= {
    var s: String = ""
    for (elm<-list) s=s+elm+" "
    return s
  }
}

object Test{
  protected var male = true

  def main(args: Array[String]): Unit = {
    val al      = new Man("Al")
    val bob     = new Man("Bob")
    val alice   = new Woman("Alice")
    val barbara = new Woman("Barbara")

    al.preferred      = alice
    bob.preferred     = barbara
    alice.preferred   = bob
    barbara.preferred = al

    val men   = Set(al, bob)
    val women = Set(alice, barbara)

    val m = new Matching()
    //var proposers=women

    var proposers: Set[_ <:Individual] = Set[Individual]()
    if (male) proposers = men
    else proposers = women

    while (!proposers.isEmpty) {
      for(proposer <- proposers) {
        val proposer=proposers.head
        if (proposer.isInstanceOf[Man])
          m.add(new Marriage(
            proposer.asInstanceOf[Man],
            proposer.preferred.asInstanceOf[Woman]
          )) 
        else 
          m.add(new Marriage(
            proposer.asInstanceOf[Woman],
            proposer.preferred.asInstanceOf[Man]
          ))
        proposers-=proposer//There is an error here
      } 
    }

    println(m)
  }
}

Answer 1

This code is messy. It's poorly formatted, it mixes tabs and spaces, and it uses mutability even in the most trivial of places where a functional solution requires little thought.

This code also won't scale internationally to countries where same-sex marriage is a possibility.

Working from the top down...

I suspect you'll never want to directly instantiate an Individual, only ever a Man or a Woman. So a algebraic data type makes more sense, this is done with a sealed trait and case class subtypes.

I'll also drop the preferred property, as it can lead to circular references. Dealing with this in immutable data is beyond the level I'm willing to go in this answer.

sealed trait Individual {
  def name: String
  override def toString(): String=name
}

//as it's a case class, `name` becomes a val,
//which implements the abstract `def name` from the trait
case class Man(name: String) extends Individual

case class Woman(name: String) extends Individual

Marriage can also be a case class, and let's drop the clumsy duplication of class parameters into vals - it's just pointless boilerplate. This is also a good time to move the auxiliary constructor to a factory method in the companion object:

case class Marriage(man: Man, woman: Woman) {      
  override def toString(): String = man + "--" + woman
}
object Marriage {
  def apply(w: Woman, m: Man) = new Marriage(m,w)
}

Matching is almost pointless, an entire class just to wrap a List? This kind of thing made sense in pre-Generics Java, but not any more. I'll keep it anyway (for now) so I can fix up that toString implementation, which is painfully mutable and uses return for no good reason:

case class Matching(){
  private var list: List[Marriage] = Nil
  def add(m: Marriage): Unit = { list ::= m }
  override def toString() = list.mkString(" ")
}

Finally, the "meat" of the problem. Comments are inline, but you'll note that I don't need (or use) Matching. It's replaced in its entirety by the final println

object Test{
  //better name, and a val (because it never changes)
  protected val menPropose = true

  def main(args: Array[String]): Unit = {

    // `new` not required for case classes
    val al      = Man("Al")
    val bob     = Man("Bob")
    val alice   = Woman("Alice")
    val barbara = Woman("Barbara")

    // remember how preference was removed from `Individual`?
    val mprefs = Map( al -> alice, bob -> barbara )
    val fprefs = Map( alice -> bob, barbara -> al )

    val men   = Set(al, bob)
    val women = Set(alice, barbara)

    // nicely immutable, and using the returned value from if/else
    val proposers = if (menPropose) men else women

    // no while loop, name shadowing, or mutability.
    // just a simple for-comprehension
    val marriages = for(proposer <- proposers) yield {
      //pattern-matching beats `isInstanceOf`... every time
      proposer match {
        case m: Man => Marriage(m, mprefs(m))
        case f: Woman => Marriage(f, fprefs(f))
      }
    }

    println(marriages mkString " ")
  }
}

There's more that can be done here, way more. What of same-sex relationships? What if two or more people share the same preference? What if someone has no preference?

I could also encode the type of someone's preference into Individual instances. But that's getting a bit more advanced.