Applying property based testing for various algorithms using Scala check

Question
1

I am trying to use property based testing for this program. But I am not sure how to go about it or if it is even appropriate to use here? I have done property based testing for this program. But that is just an implementation of merge sort and using property based testing seems natural there.

But I am not able to comprehend applying property based testing to a lot of other programs (Eg :- functions that take in Maps as arguments with type parameters, functions that take root node of a tree as a parameter etc)

2

I’m often struggling with property-based testing, too.

Generating instances of complex data types (like custom trees you mention above) works beautifully with generators. As for generic types I don’t know a solution - one can express the properties with full generics, but for running the checks one needs to specify concrete types. I usually choose a handful “pars pro toto”. If there’s a better way, I’d love to hear about it.

The biggest problem for me usually is finding the “laws” for the concepts (hard), and expressing them in a way that doesn’t copy the implementation under test or provide a full-fledged alternative implementation (even harder).

For example, the property I naively came up with for your code is this:

def mergeProp[T : Arbitrary : Cogen]: Prop =
  Prop.forAll { (ms: Seq[Map[String, T]], f: (T, T) => T) =>
    ms.nonEmpty ==> {
      val allKeys = ms.map(_.keySet).reduce(_ ++ _)
      def expVal(k: String): T = {
        val allVals = ms.flatMap(_.get(k).toSeq)
        allVals.tail.foldLeft(allVals.head)(f)
      }
      val res = MergeMaps.merge(f, ms:_*)
      res.keySet == allKeys && allKeys.forall(k => res(k) == expVal(k))
    }
  }

(EDIT: minor code gardening)

…where the last line could be replaced with:

      val exp = allKeys.map(k => (k, expVal(k))).toMap
      res == exp

…showing clearly it’s an implementation rather than a spec. :confused:

Any ideas for more “abstract” properties?

Best regards,
Patrick

3

Hey, I think it is a good start! The generator thing is really useful :slight_smile:

Yeah, I agree with you that it tilts more on the side of implementation detail.

A question here though,
Can this be replaced

    allVals.tail.foldLeft(allVals.head)(f)

with
allVals.reduce.(f) ?
Also, are you interested to contribute to the repo? You could push your example test just in case you are interested :slight_smile:

4

Yes, indeed, much better. I’d probably explicitly use reduceLeft here (of which reduce is just an alias), just to make it obvious that f is not guaranteed to be associative.

Sure, why not? :slight_smile: PR sent.

Just a few unrelated notes on the project:

  • I’d suggest to use proper package names based on a domain you own (if in doubt: io.github.ashwinbhaskar should do as a prefix, i.e. io.github.ashwinbhaskar.scalaway.divideandconquer, etc.)
  • Test cases should also reside in proper packages (usually the same as the class under test).
  • The .idea folder shouldn’t be checked in, that’s part of the individual local setup.

Best regards,
Patrick

5

Cool! Accepted the PR. Will make the changes that you suggested soon!

6

Just for the kicks, another variant: More fine-grained/separated properties, easier sharing of properties for varying generic types.

import org.scalacheck._

class MergeMapsProperties extends Properties(name = "MergeMaps") {

  val builders: Seq[Builder[_]] =
    Seq(
      new Builder[Int]("int"),
      new Builder[String]("string"),
      new Builder[Map[String, Int]]("map"),
    )

  for {
    b <- builders
    (n, p) <- b.props
  } property(n) = p

  class Builder[T : Arbitrary : Cogen](protected val ext: String) {

    private type M = Map[String, T]

    def props: Seq[(String, Prop)] = {
      import Prop._
      import MergeMaps._
      Seq(
        "chains" ->
          forAll { (ms: Seq[M], m: M, f: (T, T) => T) =>
            merge(f, merge(f, ms: _*), m) == merge(f, ms :+ m: _*)
          },

        "keys" ->
          forAll { (a: M, b: M, f: (T, T) => T) =>
            merge(f, a, b).keySet == (a.keySet ++ b.keySet)
          },

        "vals" ->
          forAll { (a: M, b: M, f: (T, T) => T) =>
            val merged = MergeMaps.merge(f, a, b)
            def cmb(x: M, y: M): Boolean = x.keySet.intersect(y.keySet).forall(k => merged(k) == f(x(k), y(k)))
            def id(x: M, y: M): Boolean = x.keySet.diff(y.keySet).forall(k => merged(k) == x(k))
            cmb(a, b) && id(a, b) && id(b, a)
          }
      ).map { case (n, p) => s"$n/$ext" -> p }
    }

  }

}

EDIT: minor code gardening

No idea if this brings me any closer to property-based testing satori, or if it leads me farther astray from it. :slight_smile:

Best regards,
Patrick

7

Check this contribution by a Haskell guy. He seems to have approached property based testing differently.

8

I’m not a Haskell pro, so I may be missing something crucial, but this looks rather odd to me. (I also couldn’t get the cabal project to build/test at all at a quick stab.)

The transformBSTcommutes property doesn’t seem to type check - transformBST has type Tree a -> Tree a, but here it is applied to arbitrary Traversable instances. (There seem to be other problems across the code, as well.)

If this property worked, it wouldn’t specify much about transformBST - the identity function would trivially satisfy it, for example. On the other hand, one could imagine values for f that would leave the property unsatisfied.

9

Ahh okay. I did not try it out. As the PR is not yet merged. Seemed interesting looking at the code. I guess I will look into it a bit more deeply and try running it and get back to you on this.