Type Checking Error that I dont understand

On Sunday 06 September 2009 15:06:18 antiflirt wrote:
> Hello,
> Here is my problem :
>
> val A = List(List(1,2),List(3,4))
> val B = A.foldLeft(List())(_++_)
>
> That code seems legitimate to me (where am I wrong ??)
> But the compiler complains : "error type mismatch; found List[Int] required
> Iterable[Nothing]"
>
> Can someone tell me what's wrong ?
>
1. You should check out Iterable.flatten:
scala> val A = List(List(1,2),List(3,4))
A: List[List[Int]] = List(List(1, 2), List(3, 4))

scala> A.flatten
res0: List[Int] = List(1, 2, 3, 4)

2. You need to use something other than "List()" because "List()" gets the
type "List[Nothing]", and a "List[Int] ++ List[Nothing]" cannot become a
List[Int], so that's why the types aren't compatible. Try using:
scala> val B = A.foldLeft(List[Int]())(_ ++ _)
B: List[Int] = List(1, 2, 3, 4)

...instead

David Flemström
david.flemstrom@gmail.com

scala> val A = List(List(1,2),List(3,4))A: List[List[Int]] = List(List(1, 2), List(3, 4))
scala> val B = A.foldLeft(List[Int]())(_++_)B: List[Int] = List(1, 2, 3, 4)
scala> 

On Sun, Sep 6, 2009 at 9:06 AM, antiflirt <dubois_ivan@yahoo.fr> wrote:

Hello,
Here is my problem :

val A = List(List(1,2),List(3,4))
val B = A.foldLeft(List())(_++_)

That code seems legitimate to me (where am I wrong ??)
But the compiler complains : "error type mismatch; found List[Int] required
Iterable[Nothing]"

Can someone tell me what's wrong ?
--
View this message in context: http://www.nabble.com/Type-Checking-Error-that-I-dont-understand-tp25317638p25317638.html
Sent from the Scala mailing list archive at Nabble.com.

--
http://erikengbrecht.blogspot.com/

Thank you both !
Indeed A.flatten() is also much simpler !

On Sun, Sep 6, 2009 at 9:06 AM, antiflirt <dubois_ivan@yahoo.fr> wrote:

Hello,
Here is my problem :

val A = List(List(1,2),List(3,4))
val B = A.foldLeft(List())(_++_)

One more solution that hasn't yet come up: use flatMap.  It's intermediate in generality between foldLeft and flatten, and usually doesn't require explicit type declarations (e.g. i:List[Int] is not required--but a simple _ doesn't work for copying, but _.reverse would be okay if that's what you wanted).

val a = List(List(1,2),List(3,4))
val b = a.flatMap(i=>i)

  --Rex

flatMap is a very important one to know about.  But in case anyone is thinking about using it here, it's just wastefully extravagant.

Conceptually,  a.flatMap(i=>i)
is the same as:  a.map(i=>i).flatten
but map(i => i) is just the identity transform, and so definitely not needed.


On Sun, Sep 6, 2009 at 7:44 PM, Rex Kerr <ichoran@gmail.com> wrote:

On Sun, Sep 6, 2009 at 9:06 AM, antiflirt <dubois_ivan@yahoo.fr> wrote:

Hello,
Here is my problem :

val A = List(List(1,2),List(3,4))
val B = A.foldLeft(List())(_++_)

One more solution that hasn't yet come up: use flatMap.  It's intermediate in generality between foldLeft and flatten, and usually doesn't require explicit type declarations (e.g. i:List[Int] is not required--but a simple _ doesn't work for copying, but _.reverse would be okay if that's what you wanted).

val a = List(List(1,2),List(3,4))
val b = a.flatMap(i=>i)

  --Rex

Point taken--it's overkill to use flatMap for a flatten, but foldLeft is even more wastefully extravagant: you need to join lists instead of elements.  I believe the underlying implementation doesn't actually create a new list with map before flattening it; it does both operations in one step, so it's like a flatten with an unnecessary method call on every element in the main list.
  --Rex

On Sun, Sep 6, 2009 at 3:04 PM, Kevin Wright <kev.lee.wright@googlemail.com> wrote:

flatMap is a very important one to know about.  But in case anyone is thinking about using it here, it's just wastefully extravagant.

On Sun, Sep 6, 2009 at 7:44 PM, Rex Kerr <ichoran@gmail.com> wrote:

On Sun, Sep 6, 2009 at 9:06 AM, antiflirt <dubois_ivan@yahoo.fr> wrote:

Hello,
Here is my problem :

val A = List(List(1,2),List(3,4))
val B = A.foldLeft(List())(_++_)

One more solution that hasn't yet come up: use flatMap.  It's intermediate in generality between foldLeft and flatten, and usually doesn't require explicit type declarations (e.g. i:List[Int] is not required--but a simple _ doesn't work for copying, but _.reverse would be okay if that's what you wanted).

val a = List(List(1,2),List(3,4))
val b = a.flatMap(i=>i)

  --Rex

On Sun, Sep 6, 2009 at 9:08 PM, Rex Kerr <ichoran@gmail.com> wrote:

Point taken--it's overkill to use flatMap for a flatten, but foldLeft is even more wastefully extravagant: you need to join lists instead of elements.  I believe the underlying implementation doesn't actually create a new list with map before flattening it; it does both operations in one step, so it's like a flatten with an unnecessary method call on every element in the main list.
  --Rex

Definitely, foldLeft for this kind of problem should be strictly reserved for those extra special rare cases where all you really want is a hotter processor:
http://www.phys.ncku.edu.tw/~htsu/humor/fry_egg.html
 

On Sun, Sep 6, 2009 at 3:04 PM, Kevin Wright <kev.lee.wright@googlemail.com> wrote:

flatMap is a very important one to know about.  But in case anyone is thinking about using it here, it's just wastefully extravagant.

On Sun, Sep 6, 2009 at 7:44 PM, Rex Kerr <ichoran@gmail.com> wrote:

On Sun, Sep 6, 2009 at 9:06 AM, antiflirt <dubois_ivan@yahoo.fr> wrote:

Hello,
Here is my problem :

val A = List(List(1,2),List(3,4))
val B = A.foldLeft(List())(_++_)

One more solution that hasn't yet come up: use flatMap.  It's intermediate in generality between foldLeft and flatten, and usually doesn't require explicit type declarations (e.g. i:List[Int] is not required--but a simple _ doesn't work for copying, but _.reverse would be okay if that's what you wanted).

val a = List(List(1,2),List(3,4))
val b = a.flatMap(i=>i)

  --Rex

Thank you all for your explanations. I agree I should use flatten instead of
foldLeft.
But there is still something strange. In the Scala library, I see that
Nothing is at the bottom of the type hierarchy, wich means thats it is
consided a subtype of any other type.
So List[Int]++List[Nothing] could be considered as List[Int] since nothing
is an Int, right ?
More generaly, if A is a subtype of B, shouldnt List[A]++List[B] be of type
List[B] ?
Where am I wrong ?

David Flemström wrote:
>
>
> On Sunday 06 September 2009 15:06:18 antiflirt wrote:
>> Hello,
>> Here is my problem :
>>
>> val A = List(List(1,2),List(3,4))
>> val B = A.foldLeft(List())(_++_)
>>
>> That code seems legitimate to me (where am I wrong ??)
>> But the compiler complains : "error type mismatch; found List[Int]
>> required
>> Iterable[Nothing]"
>>
>> Can someone tell me what's wrong ?
>>
> 1. You should check out Iterable.flatten:
> scala> val A = List(List(1,2),List(3,4))
> A: List[List[Int]] = List(List(1, 2), List(3, 4))
>
> scala> A.flatten
> res0: List[Int] = List(1, 2, 3, 4)
>
> 2. You need to use something other than "List()" because "List()" gets the
> type "List[Nothing]", and a "List[Int] ++ List[Nothing]" cannot become a
> List[Int], so that's why the types aren't compatible. Try using:
> scala> val B = A.foldLeft(List[Int]())(_ ++ _)
> B: List[Int] = List(1, 2, 3, 4)
>
> ...instead
>
> David Flemström
> david.flemstrom@gmail.com
>
>

On Sun, Sep 6, 2009 at 10:26 PM, antiflirt wrote:
>
> Thank you all for your explanations. I agree I should use flatten instead of
> foldLeft.
> But there is still something strange. In the Scala library, I see that
> Nothing is at the bottom of the type hierarchy, wich means thats it is
> consided a subtype of any other type.
> So List[Int]++List[Nothing] could be considered as List[Int] since nothing
> is an Int, right ?
> More generaly, if A is a subtype of B, shouldnt List[A]++List[B] be of type
> List[B] ?
> Where am I wrong ?
>

You are right, except for limitations in Scala's type inference.

For a method def foldLeft[A](l: A)(op: (A,T)=>A), the compiler has to
resolve the type argument A on the *first* argument list only. It sees
List[Nothing], and assumes that A is List[Nothing]. It then decides
that op must be of type (List[Nothing],T)=>List[Nothing], where T is
the type of the collection. The type inferencer sees that op actually
returns List[Int], but it can't backtrack to fix the issue. So you as
a coder have to let foldLeft know in the first argument that you want
List[Int].

HTH,