Implementing NPlusK patterns in Scala

Question

I thought I could implement n+k patterns as an active pattern in scala via unapply, but it seems to fail with unspecified value parameter: k

object NPlusK {
    def apply(n : Int, k : Int) = {
        n + k
    }    

    def unapply(n : Int, k : Int) = {
        if (n > 0 && n > k) Some(n - k) else None
    }
}

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

    }

    def fac(n: Int) : BigInt = {
        n match {
            case 0 => 1
            case NPlusK(n, 1) => n * fac(n - 1)
        }
    }
}

Is it possible to implement n+k patterns in Scala and in that event how?

Have a look at [this question](http://stackoverflow.com/questions/6738577/matching-with-custom-combinations-operators/6738708) — dhg, May 11 '12 at 20:32

score 4 · Answer 1 · edited May 23 '17 at 12:04

4

You should look at this question for a longer discussion, but here's a short adaptation for your specific case.

An unapply method can only take one argument, and must decide from that argument how to split it into two parts. Since there are multiple ways to divide some integer x into n and k such that x = n + k, you can't use an unapply for this.

You can get around it by creating a separate extractors for each k. Thus, instead of NplusK you'd have Nplus1, Nplus2, etc since there is exactly one way to get n from x such that x = n + 1.

case class NplusK(k: Int) {
  def unapply(n: Int) = if (n > 0 && n > k) Some(n - k) else None
}

val Nplus1 = NplusK(1)

val Nplus1(n) = 5  // n = 4

So your match becomes:

    n match {
        case 0 => 1
        case Nplus1(n) => n * fac(n - 1)
    }

edited May 23 '17 at 12:04

Community

1
1

answered May 11 '12 at 20:46

dhg

52,383
8
123
144

Why is it that you can't match on `Nplus(1)(n)`? Is there some way to make it work without declaring `Nplus1` explicitly? – Dan Burton May 12 '12 at 23:42
1

The `Nplus(1)(n)` syntax is not possible because Scala does not allow expressions as extractors. There's some discussion on other SO questions about why this is, but as I recall it has to do with ambiguity in figuring out what is supposed to be bound by the match. – dhg May 12 '12 at 23:49

score 3 · Accepted Answer · answered May 11 '12 at 20:35

Deconstructor unapply does not work this way at all. It takes only one argument, the matched value, and returns an option on a tuple, with as many elements as there are arguments to the your pattern (NPlusK). That is, when you have

(n: Int) match {
   ...
   case NPlusK(n, 1)

It will look for an unapply method with an Int (or supertype) argument. If there is such a method, and if the return type is a Tuple2 (as NPlusK appears with two arguments in the pattern), then it will try to match. Whatever subpattern there are inside NPlusK (here the variable n, and the constant 1), will not be passed to unapply in anyway (what do you expect if you write case NPlusK(NPlusK(1, x), NPlusK(1, y))?). Instead, if unapply returns some tuple, then each element of the tuple will be matched to the corresponding subpattern, here n which always matches, and 1 which will match if the value is equal to 1.

You could write

def unapply(n: Int) = if (n > 0) Some((n-1, 1)) else None.

That would match when your NPlusK(n, 1). But that would not match NPlusK(n, 2), nor NPlusK(1, n) (except if n is 2). This does not make much sense. A pattern should probably have only one possible match. NPlusK(x, y) can match n in many different ways.

What would work would be something Peano integers like, with Succ(n) matching n+1.

I have tried and extended your proposal of using peano integers to use macros, but it seems that macros are not expanded before pattern matching is applied, any alternative ideas? otherwise I would have to wait for string interpolation to complete in 2.11 and make my own string interpolator — Yet Another Geek, May 16 '12 at 20:40
Sorry, I don't understand what you're asking. I've not looked at macro in depth yet, and I must say matching Peano integers rather than checking `if (n > 0)` looks bizarre to me except as an exercise. Maybe you should post as a new question. — Didier Dupont, May 16 '12 at 21:39
I will try and post the macro to another question as a continuation on this. — Yet Another Geek, May 18 '12 at 16:23

Implementing NPlusK patterns in Scala

2 Answers2