Pattern matching, type parameters and type erasure

Hi,
This sounds like a case for extractors :-)
How about:
def findLocation(time: Int, track: List[(Int, String)]) = {  // since we don't have parametric extractors, need to pass time into the outer class, Check    val c = new Check(time); import c._   track.sliding(2).collectFirst({       case Beginning(Has(r))  => "<at " + r.head       case End(Has(r))  => "at> " + r.last        case Between(Has(r))  => "between " + r.head + " and " + r.last   })}
/*scala> findLocation(10, List((10,"a"), (11, "b"))) res5: Option[java.lang.String] = Some(<at 10)
scala> findLocation(11, List((10,"a"), (12, "b")))res6: Option[java.lang.String] = Some(between 10 and 12)
scala> findLocation(12, List((10,"a"), (12, "b")))res7: Option[java.lang.String] = Some(at> 12)*/
You'll need the extractors I've defined below.
cheers,adriaan
// encoding of parametric extractor: checks that a pattern is a range that contains the given `time`class Check(val time: Int) {    object Has {    def unapply(r: Range): Option[Range] = if(r contains time) Some(r) else None  }}
object Beginning {  def unapply(ps: List[(Int, String)]): Option[Range] = ps match {      // no need for type ascription in these patterns: they are implied by the type of ps     case List((a, b), (c, d)) => Some(a to a)     case _ => None  }}
object End {  def unapply(ps: List[(Int, String)]): Option[Range] = ps match {     case List((a, b), (c, d)) => Some(c to c)     case _ => None  } }
object Between {  def unapply(ps: List[(Int, String)]): Option[Range] = ps match {     case List((a, b), (c, d)) => Some(a to c)     case _ => None   }}

On Wed, Sep 7, 2011 at 9:27 AM, Alan Burlison <alan.burlison@gmail.com> wrote:

I'm using a simple-but-real problem to help me find my way around the Scala syntax, please be gentle ;-)  The problem I'm using is this - I have a list of times and positions from a GPS track log, and given a time (obtained from the EXIF data in a JPEG) I want to find out the location where the photo was taken.  To simplify things so I can get started I've initially modelled the time as an integer and the position as a letter.  The simplified tracklog can therefore be modelled as a list of (time, position) tuples, e.g.

val track = List(2 -> "a", 4 -> "b", 6 -> "c", 8 -> "d");

I then use sliding() and collectFirst() on the list to find the location given a time as follows:

def findLocation(time: Int, track: List[(Int, String)]) = {
   track.sliding(2).collectFirst({
       case List((a: Int, b: String), (c: Int, d: String))
           if (time == a) => "at " + b
       case List((a: Int, b: String), (c: Int, d: String))
           if (time == c) => "at " + d
       case List((a: Int, b: String), (c: Int, d: String))
           if (time > a && time < c) => "between " + b + " and " + d
   })
}

That all works fine.  The first question I have is this: is there a way of collapsing down the repeated case patterns?  This (obviously) doesn't work:

       case List((a: Int, b: String), (c: Int, d: String))
           if (time == a) => "at " + b
           if (time == c) => "at " + d
           if (time > a && time < c) => "between " + b + " and " + d

The next question is how to replace the specific Int and String types in the version above with type parameters to make findLocation more generic - in the real application I'll be comparing java.util.Calendar objects rather than Ints.  I figured out I needed to use an implicit view bound and Comparable:

def findLocation[T <% Ordered[T], P](time: T, track: List[(T, P)]) = ...

however if I simply replace Int with T and String with P in the case statements I get warnings like this:

warning: abstract type T in type pattern T is unchecked since it is eliminated by erasure
       case List((a: T, b: P), (c: T, d: P))
                     ^
That makes perfect sense, but it's a little unsatisfying :-)  The quick fix is just to remove the types from the case statements as below:

def findLocation[T <% Ordered[T], P](time: T, track: List[(T, P)]) = {
   track.sliding(2).collectFirst({
       case List((a, b), (c, d))
           if (time == a) => "at " + b;
       case List((a, b), (c, d))
           if (time == c) => "at " + d
       case List((a, b), (c, d))
           if (time > a && time < c) => "between " + b + " and " + d
   })
}

That's kinda ok - the type parameters on the definition of findLocation ensure that the ==, < and > operators are only ever used on objects that support them (i.e. Comparable).  I found some information about Manifests and that seems like it might a the way to add the type checking back in to the case statements, but I'm not sure if it's worth the effort, and if it is I'm not sure what the syntax would look like. Advice gratefully accepted :-)

Learning this Scala thing is such fun :-)

On 09/07/11 09:47, Adriaan Moors wrote:

> This sounds like a case for extractors :-)

That sounds like a prompt to re-read that section of the PinS book,
which I have done and quite a bit more of it has clicked into place in
my head, thanks :-)

I'm struggling a little to understand how your example all 'plumbs
together', it still seems a little bit 'inside out' to me at the moment
if that makes sense.

Taking the first case, "Beginning(Has(r))", am I correct in believing
that Beginning generates a degenerate range (e.g. 10..10) and that "Has"
is then used to test if the time value encapsulated inside "new
Check(time)" falls within that range? If it does, "Has" returns the
10..10 range and then findLocation extracts the first element out with
"head", i.e. 10, which is the required result.

If Scala *did* have parametric extractors, how might that look
syntactically?

Also, the version I posted works for any search key that's Comparable,
not just integers:

scala> findLocation(5, List(2 -> "a", 4 -> "b", 6 -> "c"))
res22: Option[java.lang.String] = Some(between b and c)

scala> findLocation("t", List("a" -> 1, "m" -> 2, "z" -> 3))
res23: Option[java.lang.String] = Some(between 2 and 3)

whereas I think the version you outlined would only work where the
search key was an integer, because of the use of Range. Have I got that
right?

Thanks for taking the time to answer my questions, the climb up Mount
Scala may be steep in places, but the views more than compensate :-)

"yes" to all your questions :-) (I'd say "inside out" is the very nature of pattern matching, you're undoing what has been done when objects were constructed)

I think NumericRange may be versatile enough, Range certainly isn't, indeed.

On Wed, Sep 7, 2011 at 4:05 PM, Alan Burlison <alan.burlison@gmail.com> wrote:

If Scala *did* have parametric extractors, how might that look syntactically?

Interesting question. We'd have to change the syntax for patterns, so it's an unlikely change in the near future, but you can get a bit closer with implicits, our swiss army knife:
// implicit version of the encoding of parametric extractor: checks that a pattern is a range that contains the given `time`object Has {   def unapply(r: Range)(implicit time: Int): Option[Range] = if(r contains time) Some(r) else None }

def findLocation(time: Int, track: List[(Int, String)]) = {  implicit val t = time // for Has extractor   track.sliding(2).collectFirst({       case Beginning(Has(r)/*(time) -- not allowed explicitly, must be supplied implicitly*/)  => "<at " + r.head        case End(Has(r))  => "at> " + r.last       case Between(Has(r))  => "between " + r.head + " and " + r.last   })}

The simplest syntactic change I can think of would be to allow multiple argument lists for extractors, so that it doesn't have to be an implicit argument (i.e., it could be supplied explicitly)
cheersadriaan

On 09/07/11 15:24, Adriaan Moors wrote:

> "yes" to all your questions :-) (I'd say "inside out" is the very nature of
> pattern matching, you're undoing what has been done when objects were
> constructed)

That's a useful way of thinking about it, thanks for the insight.

> I think NumericRange may be versatile enough, Range certainly isn't, indeed.

In my case I'm going to be searching over java.util.Calendar objects, so
I need figure out how to rejig the code for that anyway.

>> If Scala *did* have parametric extractors, how might that look
>> syntactically?
>>
> Interesting question. We'd have to change the syntax for patterns, so it's
> an unlikely change in the near future, but you can get a bit closer with
> implicits, our swiss army knife:

[snip]

> The simplest syntactic change I can think of would be to allow multiple
> argument lists for extractors,
> so that it doesn't have to be an implicit argument (i.e., it could be
> supplied explicitly)

Thanks, interesting. Once again, implicits to the rescue, I think
perhaps there's some sort of theme developing there -)

On Wed, Sep 7, 2011 at 11:24, Adriaan Moors wrote:
>> If Scala *did* have parametric extractors, how might that look
>> syntactically?
>
> Interesting question. We'd have to change the syntax for patterns, so it's
> an unlikely change in the near future, but you can get a bit closer with
> implicits, our swiss army knife:

OMG! I never realized implicits could be used to pass parameters to extractors!

> The simplest syntactic change I can think of would be to allow multiple
> argument lists for extractors,
> so that it doesn't have to be an implicit argument (i.e., it could be
> supplied explicitly)

Looks very elegant to me. I don't recall any case in which case
X(...)(...) would be allowed, which means it wouldn't break anything
either. I know there are many, many people who would _love_ to see
such a feature in Scala. And, since implicits _are_ being passed as
parameters, it wouldn't really introduce anything new to code being
generated.