Functional Scala: Combinatoric Pattern Matching

Welcome to another episode of functional Scala!

In the last episode we were introducing ourself to the idea of Pattern matching – a powerful mechanism for operating on algebraic datatypes by examining different occurrences for a certain type separately, each within an individual case expression. So far, we only matched single values of some sum types by their given value constructors. In this episode we’re going to see how to match against a combination of sum type values.

As threatened in the last episode, imagine we need some tri-state logic for implementing a simple probabilistic model. In this model, we wanna be able to resolve some propositions to be either true or false or ‘maybe true or false‘ (we don’t know yet). Don’t you think this calls for an own datatype? There might be three different values, say True, False and Maybe. Let’s give Maybe some special honor: because it looks some kind of exceptional in relation to those well known others, we might name our new datatype Moolean. So let’s not lose any further word and first define an appropriate datatype:

sealed abstract class Moolean
case object True extends Moolean
case object False extends Moolean
case object Maybe extends Moolean

So far, this is all boring. What we have here is a simple, pure sum type, featuring three value constructors. Now things get more interesting, if we want to write some methods which operate on them. What about some pure moolean functions, which solely combine or transform some given moolean values. For a warm-up, we could implement a function not, which kind of inverts a given moolean value:

val not : Moolean => Moolean
    =
    ( mool :Moolean ) => mool match {
        case True => False
        case False => True
        case Maybe => Maybe
    }

Ahhh, it all seems familiar for True and False: we just behave like their Boolean counterpart. Inversing Maybe results into Maybe in our modell. Think like ‘Maybe true‘ gets inverted into ‘Maybe false‘ and also the other way round. Either way, it remains a Maybe. Now this is busines as usual. We just give a separate case expression for every possible value constructor, catching all possible cases for our given value mool.

Whats about combining two moolean values? Let’s say we wanna implement an own function equals which takes two moolean values and decides if they both are of the same value constructor. Let’s pretend there isn’t such a comparison for free in Scalas case classes, so we need to implement it on our own. Now, putting ourself in that difficult position, we now have to answer the question how to match against two moolean values simultaneously, since we need to match against both values within our case expressions in order to decide equality. After a short while you may get to the solution to simply express both values as a simple (ad hoc) pair and simply match against that instance of Tuple2 (which is a product type, by the way…). Observe:

val equal : ( Moolean, Moolean ) => Moolean
    =
    ( a :Moolean, b :Moolean ) => ( a, b ) match {
        case ( True, True ) => True
        case ( False, False ) => True
        case ( Maybe, Maybe ) => True
        case _ => False
    }

Ok, seems we can always put those individual values into a tuple and then match against that tuple! See how we could easily absorb all cases where both values aren’t of the same value constructor? Instead of factoring out all possible combinations, we just gathered them within our otherwise case.

Combining more than one value now gives rise for another nice application of the underscore: you can use’em not only as the all and final otherwise case, but also for merging only some different cases into one. Sounds funny? All i say is to use the underscore for some values within your tuple combination, where you don’t care about some values at all. For this to make clear, let’s say we wanna have a function and, which combines two moolean values in a conjunctive way. And the rules are as follows:

1. as soon as any of the two values is False, the whole expression evaluates to False
2. as soon as any of the two values is Maybe, the whole expression evaluates to Maybe
3. in all other cases, the whole expression evaluates to True

Note, that the order of evaluation is important. So rule 1 need to be evaluated before rule 2. And because rule 2 is going to be evaluated before rule 3, the only case for rule 3 is to match against two values of True. Fortunately, pattern matching plays into our hands, since the case expressions will be evaluated from top to bottom. See that ‘any of the two values‘ within our rules? As soon as there is one of both values matched, we really don’t care about the other one. This can be expressed like so:

val and : ( Moolean, Moolean ) => Moolean
    =
    ( a :Moolean, b :Moolean ) => ( a, b ) match {
        case ( False, _ ) => False
        case ( _, False ) => False
        case ( Maybe, _ ) => Maybe
        case ( _, Maybe ) => Maybe
        case _ => True
    }

Aaah, see the first case expression for example? There, we don’t care if the second value might be True, False or Maybe at all. As soon as the first value matches False, the whole expression evaluates to False. So in this case, we merged three cases into one. You may see the first two cases as somewhat related (just as the third and fourth case as well). They are somewhat the same, we only match against different positions within our tuple. Well, if this disturbs your eyes, or your feelings of elegance at all, you may bring them together into one single case expression, using disjunction:

val or : ( Moolean, Moolean ) => Moolean
    =
    ( a :Moolean, b: Moolean ) => ( a, b ) match {
        case ( True, _ ) | ( _, True ) => True
        case ( Maybe, _ ) | ( _, Maybe ) => Maybe
        case _ => False
    }

Condensing case expressions by disjunction makes your function even more concise. For the first case expression, we just catched all cases now, where the first or the second value’s matching True.

A simple Quarternary-Operator

If you come from Javaland, you surely have heard of the Ternary-Operator. It goes something like this:

int absoluteOfA = a > 0 ? a : -1 * a
String yesNo = (true && (false || true ) ? "yes" : "no"
Order order = selection.equals( "sell" ) ? new SellOrder() : new BuyOrder()

The ternary-Operator can be seen as an espression, which evaluates to one of two values of a certain type. The value is selected by a boolean expression, which preludes the whole ternary-expression (before the question mark). If the boolean expression evaluates to true, the whole expression evaluates to the first value (or expression) after the question mark, otherwise to the next expression (after the colon).

Because this episode would be to short otherwise, let’s see how to craft a Quarternary-Operator which evalueates to an arbitrary value of an arbitrary type , depending on a single moolean value. In this case, we not only need to state two values which gets selected depending if the moolean value (or expression which evaluates to a moolean value) is True or False. In addition to that, we need to give a third value which gets selected if the moolean expression evaluates to Maybe. Well, if you can’t imagine, here’s a little preview on how we would like our Quaternary-Operator to work:

val shouldBeTrue :String = True ? "TRUE" | "FALSE" | "MAYBE"
val shouldBeZero :Int = Maybe ? 1 | -1 | 0
val shouldBePupil : Person = False ? new Teacher | new Pupil | new Padawan

Please note, that the following solution will only take values for the three cases. We’ll see shortly (when looking at lazy evaluation) how to enhance this version for also working with expressions which evaluate to a certain value, only if selected by the preluding moolean value. For our Quarternary-Operator to work in the above drafted way, we need to leverage Scalas feature of implicit type conversion (which i’m just going to use here without any further explanation) while still relying on pure datatypes (without featuring any methods). We’re catching any moolean value by an implicit conversion, which starts a series of Quaternary-Fragments. Such a fragment will lead to the next fragment, until the whole expression is constructed. In this case, the expression can be evaluated (by pattern matching), resulting in the value which is given for the current moolean value. Just watch:

implicit def startQuarternary( mool : Moolean ) = new QuarternaryTrueReceiver( mool )

class QuarternaryTrueReceiver[+A]( mool : Moolean ){
    def ?[A]( trueValue :A ) = new QuarternaryFalseReceive( mool, trueValue )
}

class QuarternaryFalseReceiver[+A]( mool : Moolean, trueValue :A ){
    def |[B >: A]( falseValue :B ) = new QuarternaryMaybeReceiver( mool, trueValue, falseValue )
}

class QuarternaryMaybeReceiver[+A]( mool :Moolean, trueValue :A, falseValue :A ){
    def |[B >: A]( maybeValue :B ) = mool match {
        case True => trueValue
        case False => falseValue
        case Maybe => maybeValue
    }
}

See what’s going on? Whenever we try to call a method ? on a moolean value, implicit type conversion kicks in an calls our method startQuarternary. This method simply starts the chain of producing our fragments in form of separate classes which just collect the individual parts of the whole quarternary-expression. In the last Fragment QuarternaryMaybeReceiver, we’ve collected all necessary parts, so that we can pattern match against the inducing moolean expression and pick one of the given values to return.

Summary

In this episode, we saw how to pattern match against a combination of values – in our case two values of type Moolean. Of course, those values needn’t to be of the same type. You might pattern match against every combination of values of arbitrary algebraic datatypes. All is fine, as long as you put them into an appropriate tuple and than match against that tuple.

Further on, we saw how to kind of merge more than one case into one case expression. This we could achieve by – once again – applying the underscore (as a kind of placeholder) to those positions within the tuple, we’re not care about the concrete value. Another way of consolidating more than one case was to bring them together under one case expression in a disjunctive way.

Finally we crafted our own Quarternary-Operator. As you’ve seen, you’re kind of able to write your own control structures by need. Our algebraic datatype remained untouched. Instead we used implicit type conversion to start a chain for collecting the different parts of the whole expression.

Still, we only saw how pattern matching can help to structure your functions in a well-arranged way for sum types, yet. By cleverly leveraging the evaluation order of case expressions and merging different cases into one case expression we might gain very concise functions. What’s still open is operating on product types (well, we already have seen one example in this episode, which kind of sneaked in!). There, we may also need to pattern match against some values which are composed within other datatypes. That will be the topic of the next episode. Looking forward to see you again …

As threatened