For loop causing "error: type mismatch;"
Marc CARRÉ
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
| }
| }
<console>:15: error: type mismatch;
found : List[Int]
required: Int
candidates
^
<console>: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
Ruediger Keller
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É <carre...@gmail.com>:
Marc CARRÉ
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] = {
| else {
| 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] = {
| else {
| (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)
Marc CARRÉ
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.
Sébastien Bocq
def primes(maxValue: Int): List[Int] = {
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
Josh Suereth
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
}Marc CARRÉ
@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.html),
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 <joshua.suer...@gmail.com> 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...
>
>
>
>
>
>
>
> > 2011/7/6 Marc CARRÉ <carre.m...@gmail.com>
Stefan Wagner
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))
<console>:7: error: overloaded method value + with alternatives:
(Double)Double <and>
(Float)Float <and>
(Long)Long <and>
(Int)Int <and>
(Char)Int <and>
(Short)Int <and>
(Byte)Int <and>
(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-----
Ruediger Keller
Regards,
Rüdiger
2011/7/6 Stefan Wagner <hirn...@arcor.de>:
> Tschööö--->...Stefan
Daniel Sobral
> -----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))
> <console>:7: error: overloaded method value + with alternatives:
> (Double)Double <and>
> (Float)Float <and>
> (Long)Long <and>
> (Int)Int <and>
> (Char)Int <and>
> (Short)Int <and>
> (Byte)Int <and>
> (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-----
>
--
Daniel C. Sobral
I travel to the future all the time.
Jim McBeath
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] <http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Scala>
[2] <http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Haskell>
[3] <http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf>
--
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 <hirn...@arcor.de>
> To: scala-l...@googlegroups.com
> Subject: Re: [scala-language] Re: For loop causing "error: type mismatch;"
Florian Hars
> About the example from the API (for the lazy ones:
> http://www.scala-lang.org/api/current/scala/collection/immutable/Stream.html),
> 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.
--
#!/bin/sh -
set - `type -p $0` 'tr [a-m][n-z]RUXJAKBOZ [n-z][a-m]EH$W/@OBM' fu XUBZRA.fvt\
angher echo;while [ "$5" != "" ];do shift;done;$4 "gbhpu $3;fraqznvy sKunef.q\
r<$3&&frq -a -rc "`$4 "$0"|$1`">$3;rpub 'Jr ner Svt bs Obet.'"|$1|`$4 $2|$1`