Checking if two byte arrays are the same

Question

I have a method to compare two byte arrays. The code is Java-style, and there are many if-elses.

def assertArray(b1: Array[Byte], b2: Array[Byte]) {
  if (b1 == null && b2 == null) return;
  else if (b1 != null && b2 != null) {
    if (b1.length != b2.length) throw new AssertionError("b1.length != b2.length")
    else {
      for (i <- b1.indices) {
        if (b1(i) != b2(i)) throw new AssertionError("b1(%d) != b2(%d)".format(i, i))
      }
    }
  } else {
    throw new AssertionError("b1 is null while b2 is not, vice versa")
  }
}

I have tried as following, but it's not simplified the code much:

(Option(b1), Option(b2)) match {
    case (Some(b1), Some(b2)) => if ( b1.length == b2.length ) {
       for (i <- b1.indices) {
        if (b1(i) != b2(i)) throw new AssertionError("b1(%d) != b2(%d)".format(i, i))
       }
    } else {
       throw new AssertionError("b1.length != b2.length")
    }
    case (None, None) => _
    case _ => throw new AssertionError("b1 is null while b2 is not, vice versa")
}

Answer 1

Part of the problem is all the exceptions. There are better ways of handling exceptions, such as Scalaz Validation or Lift's Box. Scala itself comes with Either, which isn't particularly flexible.

On the other hand, you are not returning anything, which actually turns the whole code into a reverse Option: you either have Some(exception) or None.

Now, the test itself, except for checking for nulls, has a name in Scala: sameElements. Only it will not tell you what the problem was.

I can think of two ways of handling it. The first is just a small improvement on your pattern matching:

def assertArray(b1: Array[Byte], b2: Array[Byte]) = (Option(b1), Option(b2)) match {
  case (None, None) =>
  case (None, _) | (_, None) => throw new AssertionError("b1 is null while b2 is not, vice versa")
  case (Some(b1), Some(b2)) if b1.length == b2.length =>
    (b1, b2).zipped.map(_ == _)
    .zipWithIndex.find(!_._1)
    .foreach { 
      case (_, i) => throw new AssertionError("b1(%d) != b2(%d)".format(i, i))
    }
  case _ => throw new AssertionError("b1.length != b2.length")
}

The other way would be to turn the problem around completely. It would be like this:

def assertArray(b1: Array[Byte], b2: Array[Byte]) = {
  def isOneNull = 
    if ((b1 eq null) ^ (b2 eq null)) Some("b1 is null while b2 is not, vice versa")
    else None

  def areSizesDifferent =
    if (b1.length != b2.length) Some("b1.length != b2.length")
    else None

  def haveDifferentElements =
    (b1, b2).zipped.map(_ == _)
    .zipWithIndex.find(!_._1)
    .map { case (_, i) => "b1(%d) != b2(%d)" format (i, i) }

  def areTheyDifferent =
    if ((b1 ne null) && (b2 ne null)) areSizesDifferent orElse haveDifferentElements
    else isOneNull

  areTheyDifferent foreach (msg => throw new AssertionError(msg))
}

This is longer, and handles nullness in two separate places, and doesn't protect against nullness, but I think it reads much better. To get more than this I need Scalaz:

def assertArray(b1: Array[Byte], b2: Array[Byte]) = {
  def isOneNull = 
    (b1 eq null) ^ (b2 eq null) option "b1 is null while b2 is not, vice versa"

  def areTheyDifferent = 
    Option(b1) <|*|> Option(b2) flatMap {
      case (b1, b2) =>
        def areSizesDifferent = b1.length != b2.length option "b1.length != b2.length"

        def haveDifferentElements =
          (b1, b2).zipped.map(_ == _)
          .zipWithIndex.find(!_._1)
          .map { case (_, i) => "b1(%d) != b2(%d)" format (i, i) }

        areSizesDifferent orElse haveDifferentElements
    } orElse isOneNull

  areTheyDifferent foreach (msg => throw new AssertionError(msg))
}

Or, to go more full-blown with Scalaz:

def assertArray(b1: Array[Byte], b2: Array[Byte]) = {
  type Params = (Array[Byte], Array[Byte])
  type Func = Params => Option[String]

  def isOneNull = 
    (b1 eq null) ^ (b2 eq null) option "b1 is null while b2 is not, vice versa"

  def areSizesDifferent: Func = {
    case (b1, b2) => b1.length != b2.length option "b1.length != b2.length"
  }

  def haveDifferentElements: Func = {
    case (b1, b2) =>
      (b1, b2).zipped.map(_ == _)
      .zipWithIndex.find(!_._1)
      .map { case (_, i) => "b1(%d) != b2(%d)" format (i, i) }
  }

  def areTheyDifferent =
    Option(b1) <|*|> Option(b2) flatMap (
      areSizesDifferent |@| haveDifferentElements
      apply (_ orElse _)
    ) orElse isOneNull

  areTheyDifferent foreach (msg => throw new AssertionError(msg))
}

Scala has an unfortunate overhead compared to Haskell to do these things. Also, Scalaz will be able to do a bit more in the next version, but this works with 6.0.

The gain with Scalaz is not, however, legibility or conciseness (in this code, anyway), but of composition. For instance, in the current Scalaz we can abstract most of the body of areTheyDifferent like this:

def composeFM[M[_]:Plus, F[_]:Applicative, B](f: F[M[B]], g: F[M[B]]): F[M[B]] = 
  (f |@| g)(_ <+> _)
type FAB[x] = Array[Byte] => x
def areTheyDifferent = (
    Option(b1) <|*|> Option(b2) 
    flatMap composeFM[Option, FAB, Int](areSizesDifferent, haveDifferentElements)
    orElse isOneNull
)

Note that composeFM doesn't know a thing about Option or Function1 -- it applies to the pattern.

Well, anyway, take your pick. Sometimes a problem just isn't worth the trouble, but it is useful to know how to handle the trouble anyway.

Answer 2

I am not fluent in Scala, but Array is just a thin layer over Java, so List might be cleaner. In Java Arrays.equals(b1, b2) would be used, so delegate to java.