For loop causing "error: type mismatch;"

Hi,

I think you have a problem with semicolon inference.

The following is parsed wrong, because of your (superfluous) call to toList.

for (i <- (2 to scala.math.sqrt(maxValue).toInt + 1))
candidates = candidates.filter(j => (j == i) || (j % i != 0)) toList
candidates

toList is nullary, but during semicolon inference Scala doesn't know
that yet and parses the code as if toList was unary:

for (i <- (2 to scala.math.sqrt(maxValue).toInt + 1))
candidates = candidates.filter(j => (j == i) || (j % i !=
0)).toList(candidates)

You have multiple choices here: use braces for the for body, use a
semicolon, remove the toList call or insert a blank line.

I would recommend to omit the call to toList, as it serves no purpose
anyway, and additionally put the for body in braces (personal
preference). The following compiles fine:

def primes(maxValue: Int): List[Int] = {
if (maxValue < 2)
Nil
else {
var candidates = List.range(2, maxValue + 1)
for (i <- 2 to scala.math.sqrt(maxValue).toInt + 1) {
candidates = candidates.filter(j => (j == i) || (j % i != 0))
}
candidates
}
}

Also, you might consider using foldLeft instead of the for
comprehension, for a more functional approach.

Regards,
Rüdiger

2011/7/3 Marc CARRÉ :
> Hi,
>
> I'm a beginner at programming in Scala so it may be a mistake from me
> (in that case, I apologize) but could someone explain the below?
>
> I've tried a few things, less "inlining", different indentation,
> ranges instead of "2 to maxValue toList" and vice versa, even
> different implementation, but I'm just stuck at the moment.
> Especially since I thought the way I declared the type returned was
> explicit:
>     def primes(maxValue: Int): List[Int] = { ... }
> and since the for loop works just fine outside of the method.
>
> Cheers,
>
> Marc.
>
>
> Works fine:
>    scala> val maxValue = 30
>    maxValue: Int = 30
>
>    scala>       var candidates = List.range(2, maxValue+1)
>    candidates: List[Int] = List(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
> 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
> 30)
>
>    scala>       for (i <- (2 to scala.math.sqrt(maxValue).toInt + 1))
>         |         candidates = candidates.filter(j => (j == i) || (j
> % i != 0)) toList
>
>    scala> candidates
>    res15: List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
>
> Doesn't work:
>    scala>   def primes(maxValue: Int): List[Int] = {
>         |     if (maxValue < 2) Nil
>         |     else {
>         |       var candidates = List.range(2, maxValue+1)
>         |       for (i <- (2 to scala.math.sqrt(maxValue).toInt + 1))
>         |         candidates = candidates.filter(j => (j == i) || (j
> % i != 0)) toList
>         |       candidates
>         |     }
>         |   }
>    :15: error: type mismatch;
>     found   : List[Int]
>     required: Int
>                 candidates
>                 ^
>    :13: error: type mismatch;
>     found   : Unit
>     required: List[Int]
>                 for (i <- (2 to scala.math.sqrt(maxValue).toInt + 1))
>
> Maven also complain about the same, so I guess it's not proper to the
> way the console compiles on demand:
> [ERROR] /Volumes/DATA/tech/workspace/ML-Scala/src/main/scala/org/
> marccarre/ml/scala/math/Math.scala:33: error: type mismatch;
> [INFO]  found   : List[Int]
> [INFO]  required: Int
> [INFO]       candidates
> [INFO]       ^
> [ERROR] /Volumes/DATA/tech/workspace/ML-Scala/src/main/scala/org/
> marccarre/ml/scala/math/Math.scala:31: error: type mismatch;
> [INFO]  found   : Unit
> [INFO]  required: List[Int]
> [INFO]       for (i <- (2 to scala.math.sqrt(maxValue).toInt + 1))
> [INFO]              ^
> [ERROR] two errors found
>

Many thanks Rüdiger!

After a few tries I managed to understand foldLeft and come up with a
more functional implementation, I hope the below can help someone
else.
Not sure yet about the complexity of these "cool" operators and I
wonder how efficient it is compared to appending to a list. I might
benchmark it a bit later.
Anyway, here is the result. Feel free to comment on the style!

Cheers,

Marc.

scala> def primesOldSkoolWay(maxValue: Int): List[Int] = {
| if (maxValue < 2) Nil
| else {
| var candidates = (2 to maxValue toList)
| val upperBound = scala.math.sqrt(maxValue).toInt + 1
| for (i <- (2 to upperBound)) {
| candidates = candidates.filter(candidate => (candidate
== i) || (candidate % i != 0))
| }
| candidates
| }
| }
primesOldSkoolWay: (maxValue: Int)List[Int]

scala>

scala> def primesMoreFunctionalWay(maxValue: Int): List[Int] = {
| if (maxValue < 2) Nil
| else {
| val upperBound = scala.math.sqrt(maxValue).toInt + 1
| (2 to upperBound).foldLeft(2 to maxValue toList)
{ (primes, i) =>
| primes.filter(candidate => (candidate == i) ||
(candidate % i != 0))
| }
| }
| }
primesMoreFunctionalWay: (maxValue: Int)List[Int]

scala> primesOldSkoolWay(31)
res47: List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31)

scala> primesMoreFunctionalWay(31)
res48: List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31)

Sorry in advance for the double post.

For the ones curious, even though it's not very scientific, I ran the
above methods 3 times each, while measuring the time spent with
System.currentTimeMillis():
scala> primesOldSkoolWay(1000000)
scala> primesMoreFunctionalWay(1000000)
under approximately the same conditions, and here is the average time
spent:
primesOldSkoolWay: 6054 ms
primesMoreFunctionalWay: 11317 ms

Just found it quite surprising!

Cheers,

Marc.

2011/7/6 Marc CARRÉ <carre.marc@gmail.com>

Sorry in advance for the double post.

For the ones curious, even though it's not very scientific, I ran the
above methods 3 times each, while measuring the time spent with
System.currentTimeMillis():
   scala> primesOldSkoolWay(1000000)
   scala> primesMoreFunctionalWay(1000000)
under approximately the same conditions, and here is the average time
spent:
   primesOldSkoolWay: 6054 ms
   primesMoreFunctionalWay: 11317 ms

Just found it quite surprising!

Cheers,

Marc.

Here is another one for your collection

def primes(maxValue: Int): List[Int] = {
 
  (2 to maxValue).foldLeft(Vector[Int]())({(l, i) =>
    val upperBound = scala.math.sqrt(i).toInt + 1
    if (l.takeWhile(_ < upperBound).exists(i % _ == 0)) l else l :+ i
  }).toList
 
}

Let me know how it fares against the others.
Sébastien

Why don't you use the common example found in the documentation for Streams.scala?
Also, if you plan to append to something, you should use immutable.Vector, or at the very least, mutable.ArrayBuffer (for better performance).  Defaulting to Scala list is really only a good idea if you plan to use lots of tail-recursion and treat it in a situation optimal for head-tail decomposition or prepending.
When you're computing a Sieve like this, Stream (or anything lazy) can be your friend.  *rest copied from API documentation*

object Main extends Application {

   def from(n: Int): Stream[Int] =
     Stream.cons(n, from(n + 1))

   def sieve(s: Stream[Int]): Stream[Int] =
     Stream.cons(s.head, sieve(s.tail filter { _ % s.head != 0 }))

   def primes = sieve(from(2))

   primes take 10 print
 }

I'd compare the performance of that to yours...
On Tue, Jul 5, 2011 at 8:14 PM, Sébastien Bocq <sebastien.bocq@gmail.com> wrote:

2011/7/6 Marc CARRÉ <carre.marc@gmail.com>

Sorry in advance for the double post.

For the ones curious, even though it's not very scientific, I ran the
above methods 3 times each, while measuring the time spent with
System.currentTimeMillis():
   scala> primesOldSkoolWay(1000000)
   scala> primesMoreFunctionalWay(1000000)
under approximately the same conditions, and here is the average time
spent:
   primesOldSkoolWay: 6054 ms
   primesMoreFunctionalWay: 11317 ms

Just found it quite surprising!

Cheers,

Marc.

Here is another one for your collection

def primes(maxValue: Int): List[Int] = {
 
  (2 to maxValue).foldLeft(Vector[Int]())({(l, i) =>
    val upperBound = scala.math.sqrt(i).toInt + 1
    if (l.takeWhile(_ < upperBound).exists(i % _ == 0)) l else l :+ i
  }).toList
 
}

Let me know how it fares against the others.
Sébastien

Thanks Sébastien and Josh!

@Sébastien: 1750 ms for your implementation. As Josh mentioned it,
using Vector seems to pay off.

@Josh: Thanks for pointing at Vector and Stream, I just started a few
days ago and the least I can say is that the Scala API is very rich so
I guess it will take some time to master it.
I'm progressively diving into the API, Scala books, various examples
and other blogs (nice one by the way, for the lazy ones:
http://suereth.blogspot.com).

About the example from the API (for the lazy ones:
http://www.scala-lang.org/api/current/scala/collection/immutable/Stream....),
running it on Scala 2.9.0.final, I get:
java.lang.OutOfMemoryError: Java heap space

I used toList and length, just to evaluate it using something else
than print.
scala> primes take 1000000 toList
scala> primes take 1000000 length

I'll check the details of Stream a bit later, thanks again!

On 6 juil, 01:38, Josh Suereth wrote:
> Why don't you use the common example found in the documentation for
> Streams.scala?
>
> Also, if you plan to append to something, you should use immutable.Vector,
> or at the very least, mutable.ArrayBuffer (for better performance).
>  Defaulting to Scala list is really only a good idea if you plan to use lots
> of tail-recursion and treat it in a situation optimal for head-tail
> decomposition or prepending.
>
> When you're computing a Sieve like this, Stream (or anything lazy) can be
> your friend.  *rest copied from API documentation*
>
> object Main extends Application {
>
>    def from(n: Int): Stream[Int] =
>      Stream.cons(n, from(n + 1))
>
>    def sieve(s: Stream[Int]): Stream[Int] =
>      Stream.cons(s.head, sieve(s.tail filter { _ % s.head != 0 }))
>
>    def primes = sieve(from(2))
>
>    primes take 10 print
>  }
>
> I'd compare the performance of that to yours...
> On Tue, Jul 5, 2011 at 8:14 PM, Sébastien Bocq wrote:
>
>
>
>
>
>
>
> > 2011/7/6 Marc CARRÉ
>
> >> Sorry in advance for the double post.
>
> >> For the ones curious, even though it's not very scientific, I ran the
> >> above methods 3 times each, while measuring the time spent with
> >> System.currentTimeMillis():
> >>    scala> primesOldSkoolWay(1000000)
> >>    scala> primesMoreFunctionalWay(1000000)
> >> under approximately the same conditions, and here is the average time
> >> spent:
> >>    primesOldSkoolWay: 6054 ms
> >>    primesMoreFunctionalWay: 11317 ms
>
> >> Just found it quite surprising!
>
> >> Cheers,
>
> >> Marc.
>
> > Here is another one for your collection
>
> > def primes(maxValue: Int): List[Int] = {
>
> >   (2 to maxValue).foldLeft(Vector[Int]())({(l, i) =>
> >     val upperBound = scala.math.sqrt(i).toInt + 1
> >     if (l.takeWhile(_ < upperBound).exists(i % _ == 0)) l else l :+ i
> >   }).toList
>
> > }
>
> > Let me know how it fares against the others.
> > Sébastien

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Am 06.07.2011 02:38, schrieb Josh Suereth:
> def from(n: Int): Stream[Int] =
> Stream.cons(n, from(n + 1))
> // ...
> def primes = sieve(from(2))

If I could put the '2' manually in front of that stream, I would write:

def from (n: Int): Stream[Int] =
Stream.cons (n, from (n + 2))

def primes = 2 + sieve (from (3))

to avoid about 50% of useless, even values, but:

scala> def primes : Stream [Int] = 2 + sieve (from (3))
:7: error: overloaded method value + with alternatives:
(Double)Double
(Float)Float
(Long)Long
(Int)Int
(Char)Int
(Short)Int
(Byte)Int
(java.lang.String)java.lang.String
cannot be applied to (Stream[Int])
def primes : Stream [Int] = 2 + sieve (from (3))
^

How would I do it right?

I think the method you are looking for is named "+:".

Regards,
Rüdiger

2011/7/6 Stefan Wagner :
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Am 06.07.2011 02:38, schrieb Josh Suereth:
>>    def from(n: Int): Stream[Int] =
>>      Stream.cons(n, from(n + 1))
>> // ...
>>    def primes = sieve(from(2))
>
> If I could put the '2' manually in front of that stream, I would write:
>
> def from (n: Int): Stream[Int] =
>  Stream.cons (n, from (n + 2))
>
> def primes = 2 + sieve (from (3))
>
> to avoid about 50% of useless, even values, but:
>
> scala>    def primes : Stream [Int]  = 2 + sieve (from (3))
> :7: error: overloaded method value + with alternatives:
>  (Double)Double
>  (Float)Float
>  (Long)Long
>  (Int)Int
>  (Char)Int
>  (Short)Int
>  (Byte)Int
>  (java.lang.String)java.lang.String
>  cannot be applied to (Stream[Int])
>          def primes : Stream [Int]  = 2 + sieve (from (3))
>                                       ^
>
> How would I do it right?
>
> - --
>
> Tschööö--->...Stefan
> - ---------------------------
> Don't visit my homepage at:
> http://home.arcor-online.net/hirnstrom
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.10 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
>
> iEYEARECAAYFAk4UTwAACgkQQeATqGpDnRr5tACfQKgs8gDMAbeBMu3RzPUvmEOZ
> g6gAoKBuNVTYFhgoY1Pt+2pHWl9g84bA
> =c1mc
> -----END PGP SIGNATURE-----
>

On Wed, Jul 6, 2011 at 09:03, Stefan Wagner wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Am 06.07.2011 02:38, schrieb Josh Suereth:
>>    def from(n: Int): Stream[Int] =
>>      Stream.cons(n, from(n + 1))
>> // ...
>>    def primes = sieve(from(2))
>
> If I could put the '2' manually in front of that stream, I would write:
>
> def from (n: Int): Stream[Int] =
>  Stream.cons (n, from (n + 2))
>
> def primes = 2 + sieve (from (3))

Whenever you decide to use "+" for something other than adding two
numbers or concatenating strings, don't. Either you are wrong, or you
are deprecated.

Idiomatic stream usage would be:

def primes = 2 #:: sieve (from (3))

Though the standard operator for prepending elements is:

def primes = 2 +: sieve (from (3))

I'm not sure using the latter would have the same non-strictness
guarantees of the former.

>
> to avoid about 50% of useless, even values, but:
>
> scala>    def primes : Stream [Int]  = 2 + sieve (from (3))
> :7: error: overloaded method value + with alternatives:
>  (Double)Double
>  (Float)Float
>  (Long)Long
>  (Int)Int
>  (Char)Int
>  (Short)Int
>  (Byte)Int
>  (java.lang.String)java.lang.String
>  cannot be applied to (Stream[Int])
>          def primes : Stream [Int]  = 2 + sieve (from (3))
>                                       ^
>
> How would I do it right?
>
> - --
>
> Tschööö--->...Stefan
> - ---------------------------
> Don't visit my homepage at:
> http://home.arcor-online.net/hirnstrom
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.10 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
>
> iEYEARECAAYFAk4UTwAACgkQQeATqGpDnRr5tACfQKgs8gDMAbeBMu3RzPUvmEOZ
> g6gAoKBuNVTYFhgoY1Pt+2pHWl9g84bA
> =c1mc
> -----END PGP SIGNATURE-----
>

The streams prime generator is a good and simple example of how to use
streams, but if you are looking to optimize a prime generator then
perhaps you want to use a real sieve rather than using streams. The
RosettaCode page on the Sieve in Scala [1] gives a true implementation.
The comment under the Haskell implementation [2] notes that the
"unfaithful sieve" (which is what the streams implementation is) is not
better than trial division, and includes a link to a paper discussing
the time complexity of both [3]. In that paper the author derives the
time complexity of the real sieve as O(n log log n), the unfaithful
sieve as O(n^2 / (log n)^2), and trial division as O(n^1.5 / (log n)^2).
She points out that the unfaithful algorithm is about 1000 times slower
then the real thing to find about 5000 primes.

[1]
[2]
[3]

--
Jim

On Wed, Jul 06, 2011 at 02:03:12PM +0200, Stefan Wagner wrote:
> Date: Wed, 06 Jul 2011 14:03:12 +0200
> From: Stefan Wagner
> To: scala-language@googlegroups.com
> Subject: Re: [scala-language] Re: For loop causing "error: type mismatch;"
>
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Am 06.07.2011 02:38, schrieb Josh Suereth:
> > def from(n: Int): Stream[Int] =
> > Stream.cons(n, from(n + 1))
> > // ...
> > def primes = sieve(from(2))
>
> If I could put the '2' manually in front of that stream, I would write:
>
> def from (n: Int): Stream[Int] =
> Stream.cons (n, from (n + 2))
>
> def primes = 2 + sieve (from (3))
>
> to avoid about 50% of useless, even values, but:
>
> scala> def primes : Stream [Int] = 2 + sieve (from (3))
> :7: error: overloaded method value + with alternatives:
> (Double)Double
> (Float)Float
> (Long)Long
> (Int)Int
> (Char)Int
> (Short)Int
> (Byte)Int
> (java.lang.String)java.lang.String
> cannot be applied to (Stream[Int])
> def primes : Stream [Int] = 2 + sieve (from (3))
> ^
>
> How would I do it right?
>
> - --
>
> Tschööö--->...Stefan
> - ---------------------------
> Don't visit my homepage at:
> http://home.arcor-online.net/hirnstrom
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.10 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
>
> iEYEARECAAYFAk4UTwAACgkQQeATqGpDnRr5tACfQKgs8gDMAbeBMu3RzPUvmEOZ
> g6gAoKBuNVTYFhgoY1Pt+2pHWl9g84bA
> =c1mc
> -----END PGP SIGNATURE-----

On Tue, Jul 05, 2011 at 10:52:31PM -0700, Marc CARRÉ wrote:
> About the example from the API (for the lazy ones:
> http://www.scala-lang.org/api/current/scala/collection/immutable/Stream....),
> running it on Scala 2.9.0.final, I get:
> java.lang.OutOfMemoryError: Java heap space

Well, of course, that example is stacking up a HUGE chain of recursive
Stream.cons(..., sieve(s.tail filter ...)) calls (one for each prime
found), which it cannot discard without starting to report large even
numbers as prime. That is bound to OOM eventually.

- Florian.