Scala with Generics in pattern matching - issue with erasing

m.erasure.isAssignableFrom(a.getClass) is true if
"val x:A = a" compiles

-------- Original-Nachricht --------
> Datum: Tue, 13 Dec 2011 07:03:29 -0800 (PST)
> Von: Pascal
> An: scala-user
> Betreff: [scala-user] Scala with Generics in pattern matching - issue with erasing

> Hi
> I am fairly new to Scala and discussing with some colleagues that
> already played with Scala, I just wanted to try something. Lets say it
> is purely theoretical and I have no real application in mind. But I
> would like to take this as an exercise.
>
> Lets say I have a function f: A => A, A being any kind of object. And
> I have a Collection containing heterogeneous data, including A and
> also Collection of Collection and so on.
>
> If I want to use it with an Int, I can write things as:
> scala> def testi(a:Any, f:Int => Int):Any = a match {
> | case a:Int => f(a)
> | case a:List[_] => a.map(testi(_,f))
> | case _ => a
> | }
>
> Then I create a function:
> scala> def f(x:Int):Int = x+1
> f: (x: Int)Int
>
> If i do:
> testi(10,f) I get 11
> test("aaa",f), I get aaa
> testi(List(1,2,"a",List("b",3,4)), I get List(2,3,a,List(b,4,5))
>
> Fine lets say now, I want to do the same with f:String => String, this
> is very similar and I would like something generic like:
>
> scala> def test[A](a:Any, f:A => A):Any = a match {
> | case a:A => f(a)
> | case a:List[_] => a.map(test[A](_,f))
> | case _ => a
> | }
>
> Unfortunately that does not work. I can have this working but with
> homogeneous List. But I am not satisfied with the way I did:
> scala> def test[A](a:Any, f:A => A):Any = a match {
> | case a:List[_] => a.map(test[A](_,f))
> | case a:A => f(a)
> | }
>
> Reading some posts on the Net, I was able to find some suggestions
> with implicit variable related to Manifest but was not able to solve
> totally the problem. I tried something like and variants:
>
> scala> def test[A](a:Any, f:A => A)(implicit m:Manifest[A]):Any = a
> match {
> | case a:A if m.erasure == a.asInstanceOf[AnyRef].getClass =>
> f(a)
> | case a:List[_] => a.map(test[A](_,f))
> | case _ => a
> | }
>
> Can anyone suggest a clean way to solve this problem ?
>
> Thanks in advance.
> Regards

a future(*) version of the pattern matcher will leverage manifests (when available) to perform type tests that aren't possible at run time due to erasure
for now, what you figured out is the only way to do it, afaik

adriaan
(*) well, you need not look too far in the future -- it's already in an experimental branch (https://github.com/adriaanm/scala-dev/commit/fe0413546d9bc0c62994bf4fced...), and will make its way to trunk relatively soon, though probably hidden behind -Xexperimental -Yvirtpatmat

Let me see the question from another angle: how to encode a recursive type.

In my understanding, you want to have a method that receives, either: A, List[A], List[List[A]], List[List[List[A]]]], or any other type. And returns:

1) When it receives an x:A, you want the function to return f(x).

2) When it receives a xs:List[A], or xss:List[List[A]], or xsss:List[List[List[A]]] ,...., you want the function to return xs.map(1 +), or xss.map(_.map(1 +)), and so on...

3) When it receives any other than A, say y:Any, you want to return y.

The difficulties here are to express the second point where you can't encode a List[A], List[List[A]] , List[List[List[A]]] .... in one type.
I don't know how to encode that one. Anybody ?

Anwar Rizal.



On Tue, Dec 13, 2011 at 4:03 PM, Pascal <pascohen@gmail.com> wrote:

Hi
I am fairly new to Scala and discussing with some colleagues that
already played with Scala, I just wanted to try something. Lets say it
is purely theoretical and I have no real application in mind. But I
would like to take this as an exercise.

Lets say I have a function f: A => A, A being any kind of object. And
I have a Collection containing heterogeneous data, including A and
also Collection of Collection and so on.

If I want to use it with an Int, I can write things as:
scala> def testi(a:Any, f:Int => Int):Any = a match {
    | case a:Int => f(a)
    | case a:List[_] => a.map(testi(_,f))
    | case _ => a
    | }

Then I create a function:
scala> def f(x:Int):Int = x+1
f: (x: Int)Int

If i do:
testi(10,f) I get 11
test("aaa",f), I get aaa
testi(List(1,2,"a",List("b",3,4)), I get List(2,3,a,List(b,4,5))

Fine lets say now, I want to do the same with f:String => String, this
is very similar and I would like something generic like:

scala> def test[A](a:Any, f:A => A):Any = a match {
    | case a:A => f(a)
    | case a:List[_] => a.map(test[A](_,f))
    | case _ => a
    | }

Unfortunately that does not work. I can have this working but with
homogeneous List. But I am not satisfied with the way I did:
scala> def test[A](a:Any, f:A => A):Any = a match {
    | case a:List[_] => a.map(test[A](_,f))
    | case a:A => f(a)
    | }

Reading some posts on the Net, I was able to find some suggestions
with implicit variable related to Manifest but was not able to solve
totally the problem. I tried something like and variants:

scala> def test[A](a:Any, f:A => A)(implicit m:Manifest[A]):Any = a
match {
    | case a:A if m.erasure == a.asInstanceOf[AnyRef].getClass =>
f(a)
    | case a:List[_] => a.map(test[A](_,f))
    | case _ => a
    | }

Can anyone suggest a clean way to solve this problem ?

Thanks in advance.
Regards

Sorry, slightly wrong in description:

You want a function g that receives either A, List[A],List[List[A]],
List[List[List[A]]], or any other type as the first parameter.
The second parameter is f:A=>A.

The function g returns:
1) f(x) when it receives x:A.

2) xs.map(f) , or xss.map(_.map(f)), or ...., when it receives
xs:List[A], xss.List[List[A]], xsss:List[List[List[A]]] ,...

3) y when it receives y:Any .

The problem is how to encode List[A], List[List[A]],
List[List[List[A]]],...

Anybody ?

Anwar.

On 16 déc, 10:30, Anwar Rizal wrote:
> Let me see the question from another angle: how to encode a recursive type.
>
> In my understanding, you want to have a method that receives, either: A,
> List[A], List[List[A]], List[List[List[A]]]], or any other type. And
> returns:
>
> 1) When it receives an x:A, you want the function to return f(x).
>
> 2) When it receives a xs:List[A], or xss:List[List[A]], or
> xsss:List[List[List[A]]] ,...., you want the function to return xs.map(1
> +), or xss.map(_.map(1 +)), and so on...
>
> 3) When it receives any other than A, say y:Any, you want to return y.
>
> The difficulties here are to express the second point where you can't
> encode a List[A], List[List[A]] , List[List[List[A]]] .... in one type.
> I don't know how to encode that one. Anybody ?
>
> Anwar Rizal.
>
>
>
>
>
>
>
> On Tue, Dec 13, 2011 at 4:03 PM, Pascal wrote:
> > Hi
> > I am fairly new to Scala and discussing with some colleagues that
> > already played with Scala, I just wanted to try something. Lets say it
> > is purely theoretical and I have no real application in mind. But I
> > would like to take this as an exercise.
>
> > Lets say I have a function f: A => A, A being any kind of object. And
> > I have a Collection containing heterogeneous data, including A and
> > also Collection of Collection and so on.
>
> > If I want to use it with an Int, I can write things as:
> > scala> def testi(a:Any, f:Int => Int):Any = a match {
> >     | case a:Int => f(a)
> >     | case a:List[_] => a.map(testi(_,f))
> >     | case _ => a
> >     | }
>
> > Then I create a function:
> > scala> def f(x:Int):Int = x+1
> > f: (x: Int)Int
>
> > If i do:
> > testi(10,f) I get 11
> > test("aaa",f), I get aaa
> > testi(List(1,2,"a",List("b",3,4)), I get List(2,3,a,List(b,4,5))
>
> > Fine lets say now, I want to do the same with f:String => String, this
> > is very similar and I would like something generic like:
>
> > scala> def test[A](a:Any, f:A => A):Any = a match {
> >     | case a:A => f(a)
> >     | case a:List[_] => a.map(test[A](_,f))
> >     | case _ => a
> >     | }
>
> > Unfortunately that does not work. I can have this working but with
> > homogeneous List. But I am not satisfied with the way I did:
> > scala> def test[A](a:Any, f:A => A):Any = a match {
> >     | case a:List[_] => a.map(test[A](_,f))
> >     | case a:A => f(a)
> >     | }
>
> > Reading some posts on the Net, I was able to find some suggestions
> > with implicit variable related to Manifest but was not able to solve
> > totally the problem. I tried something like and variants:
>
> > scala> def test[A](a:Any, f:A => A)(implicit m:Manifest[A]):Any = a
> > match {
> >     | case a:A if m.erasure == a.asInstanceOf[AnyRef].getClass =>
> > f(a)
> >     | case a:List[_] => a.map(test[A](_,f))
> >     | case _ => a
> >     | }
>
> > Can anyone suggest a clean way to solve this problem ?
>
> > Thanks in advance.
> > Regards

On Fri, Dec 16, 2011 at 4:30 AM, Anwar Rizal <anrizal05@gmail.com> wrote:

Let me see the question from another angle: how to encode a recursive type.

It's not the question. a is an Any.
But your question is a good one. I had a similar issue recently (related to making a CanBind typeclass for Lift).
One might be tempted to use implicits but I think you'll hit diverging implicit expansion. Something like:
sealed trait LA[A0]case class A[A0](a:A0) extends LA[A0] case class L[A0](a: LA[A0]) extends LA[A0]implicit def a2la[A0](a: A0): LA[A0] = A(a)implicit def l2la[A0, LA0 <% LA[A0]](la: LA0) = LA(la)
def f[A0, LA0 <% LA[A0]](a: A0)

That looks like a lot of gibberish, and it probably has some mistakes, but like I said, you hit a compiler error that the implicits diverge/expand infinitely or something.I noticed that Ordering.Implicits is a workaround for such a concern, forcing you to explicity import the implicits only where you need them and it's safe to do so. But other than that, I'd be interested in more information on dealing with such problems. Also I think it somehow depended on the scala version.
@Indrajit --- if you have the inclination to post more details on the CanBind problem (maybe forwarding to a new thread), it may be a good opportunity, and likely you'll get there before I get a chance.

Here's the solution to a related problem of dealing with arbitrarily nested structures, as provided by Jesper Nordenberg (on 2010-09-10, so it's over a year old now).  It looks to me like it could be applicable in this case as well, with a few alterations.

A combination of implicits and default arguments works:
case class Flat[T, U](fn: T => List[U])
implicit def recFlattenFn[T, U] (implicit f: Flat[T, U] = Flat((l: T) => List(l))) =   Flat((l: List[T]) => l.flatMap(f.fn))
def recFlatten[T, U](l: List[T])(implicit f: Flat[List[T], U]) =   f.fn(l)
Examples:
scala> recFlatten(List(1, 2, 3)) res0: List[Int] = List(1, 2, 3)
scala> recFlatten(List(List(1, 2, 3), List(4, 5))) res1: List[Int] = List(1, 2, 3, 4, 5)
scala> recFlatten(List(List(List(1, 2, 3),   List(4, 5)), List(List(6, 7)))) res2: List[Int] = List(1, 2, 3, 4, 5, 6, 7)

On 16 December 2011 09:59, Naftoli Gugenheim <naftoligug@gmail.com> wrote:

On Fri, Dec 16, 2011 at 4:30 AM, Anwar Rizal <anrizal05@gmail.com> wrote:

Let me see the question from another angle: how to encode a recursive type.

It's not the question. a is an Any.
But your question is a good one. I had a similar issue recently (related to making a CanBind typeclass for Lift).
One might be tempted to use implicits but I think you'll hit diverging implicit expansion. Something like:
sealed trait LA[A0]case class A[A0](a:A0) extends LA[A0] case class L[A0](a: LA[A0]) extends LA[A0]implicit def a2la[A0](a: A0): LA[A0] = A(a)implicit def l2la[A0, LA0 <% LA[A0]](la: LA0) = LA(la)
def f[A0, LA0 <% LA[A0]](a: A0)

That looks like a lot of gibberish, and it probably has some mistakes, but like I said, you hit a compiler error that the implicits diverge/expand infinitely or something.I noticed that Ordering.Implicits is a workaround for such a concern, forcing you to explicity import the implicits only where you need them and it's safe to do so. But other than that, I'd be interested in more information on dealing with such problems. Also I think it somehow depended on the scala version.
@Indrajit --- if you have the inclination to post more details on the CanBind problem (maybe forwarding to a new thread), it may be a good opportunity, and likely you'll get there before I get a chance.

--
Kevin Wright
mail: kevin.wright@scalatechnology.com
gtalk / msn : kev.lee.wright@gmail.com quora: http://www.quora.com/Kevin-Wrightgoogle+: http://gplus.to/thecoda
kev.lee.wright@gmail.com twitter: @thecoda
vibe / skype: kev.lee.wrightsteam: kev_lee_wright
"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra