Scala case classes in collections

Question

Scenario: I am parsing an IL and want to convert from a stackbased representation to a CFG for instance.

My IL consists of multiple operations like PushInt(value), Pop etc. The question is now which implementation would be correct in terms of Scala. I would love to use case classes/objects or extractors so that I can write code alà

op match {
  case PushInt(x) => doSomethingWith x
  case Pop => ...
}

Now the problem exists with a sequence like PushInt(1) :: PushInt(1) :: Pop :: Pop since PushInt(1) is equal to PushInt(1) and I can not add multiple (equal) operations into a collection. However I know I am throwing some information away which is the position in the flow, but this is implicitly stored as te index in the sequence.

• One possible solution is to override the hashCode method and break the rules of equal/hashCode. I am not really happy with that.

• Another option is to have a "creation time" counter that is stored in the abstract base so that case class PushInt(value: Int) extends AbstractOp(AbstractOp.nextIndex)

• Use extractors but in that case I will miss nice features like the implementation of hashCode, equals, toString and more important the check for an exhaustive match.

So my question is now how to model my structure according to my requirements. Is any of the possible solutions "correct" in terms of Scala?

Answer 1

First, let's address the problem of finding the exact instance you want:

scala> trait AbstractOp
defined trait AbstractOp

scala> case class Pop() extends AbstractOp {
     |   override def equals(other: Any) = other match {
     |     case that: Pop => this eq that
     |     case _ => false
     |   }
     | }
defined class Pop

scala> case class PushInt(val i: Int) extends AbstractOp {
     |   override def equals(other: Any) = other match {
     |     case that: PushInt => this eq that
     |     case _ => false
     |   }
     | }
defined class PushInt

scala> val l = List(PushInt(1), PushInt(1), Pop(), Pop())
l: List[Product with AbstractOp] = List(PushInt(1), PushInt(1), Pop(), Pop())

scala> val op = l(1)
op: Product with AbstractOp = PushInt(1)

scala> println( l.indexOf( op ) )
1

That, of course, mean PushInt(1) != PushInt(1), unless it is the exact same instance of PushInt(1). It doesn't break equals/hashCode contract because a.equals(b) => a.hashCode == b.hashCode, but a.hashCode == b.hashCode doesn't imply anything. But if your only use is finding that instance, try this instead:

scala> case class Pop() extends AbstractOp
defined class Pop

scala> case class PushInt(val i: Int) extends AbstractOp
defined class PushInt

scala> val l = List(PushInt(1), PushInt(1), Pop(), Pop())
l: List[Product with AbstractOp] = List(PushInt(1), PushInt(1), Pop(), Pop())

scala> val op = l(1)
op: Product with AbstractOp = PushInt(1)

scala> println( l.findIndexOf( op eq _ ) )
1

Either way, if you reinsert that instance in the list you'll have trouble. You have to make sure that each instance you insert is unique. You might even write your own collection, either throwing an exception if a repeated instance is inserted, or make a copy of any instance passed to it (easy enough with case classes and copy method on Scala 2.8).

Answer 2

If Joa don't mind ;) Imagine a code like that:

trait AbstractOp
case class Pop() extends AbstractOp
case class PushInt(val i:Int) extends AbstractOp

now we construct a list representing a sequence of a program instructions

val l=List(PushInt(1), PushInt(1), Pop(), Pop())

First problem : you want to get the index of an operation

val op=l(1) // get the second operation for example
// now you want to get back the index for the op you are using
println( l.indexOf( op1 ) ) // you will get 0 and not 1

Second problem : you want to map each operation from the previous list to a value, this will fail since equals will not distinguish the two Pop, or the two PushInt.

P.S. Of course it is not an answer, i haven`t found how to post this under the others comments feel free to move it at the right place