https://kotlinlang.org logo
Title
s

stkent

11/06/2018, 9:31 PM
I'm trying to build a Kotlin version of the lazy prime number generator based on the Sieve of Eratosthenes from this Haskell video (10m55s):

https://www.youtube.com/watch?v=bnRNiE_OVWA&t=10m55s

I ended up here:
fun sieve(remainderSequence: Sequence<Int> = generateSequence(2) { it + 1 }): Sequence<Int> {
    val newPrime = remainderSequence.first()
    val newRemainderSequence = remainderSequence.filterNot { it % newPrime == 0 }

    return sequence {
        yield(newPrime)
    }.plus(sieve(newRemainderSequence))
}
which I thought would remain lazy, but it appears not to. What am I missing?
e

elizarov

11/06/2018, 9:33 PM
You should put all code inside
sequence { }
and instead plus use yieldAll
s

stkent

11/06/2018, 9:34 PM
Awesome, that works! What is it about
plus
that prevents this from working the same way as
yieldAll
?
plus
was marked as 'intermediate' so I thought the evaluation would still be lazy?
n

Nikky

11/06/2018, 9:40 PM
can you show the fixed code ?
s

stkent

11/06/2018, 9:40 PM
Sure!
n

Nikky

11/06/2018, 9:40 PM
i think this would be nice demo for my friends to expose them to a bit more than plain old java in school
❤️ 1
s

stkent

11/06/2018, 9:41 PM
fun sieve(remainderSequence: Sequence<Int> = generateSequence(2) { it + 1 }): Sequence<Int> {
    val newPrime = remainderSequence.first()
    val newRemainderSequence = remainderSequence.filterNot { it % newPrime == 0 }

    return sequence {
        yield(newPrime)
        yieldAll(sieve(newRemainderSequence))
    }
}
n

Nikky

11/06/2018, 9:41 PM
since they recently mentioned doing exactly this sieve of Eratosthenes using arrays
thx
s

stkent

11/06/2018, 9:42 PM
No problem 🙂
k

karelpeeters

11/06/2018, 9:57 PM
Huh. So where's the actual memory usage now? `FilteringSequence`s that just keep nesting?
s

stkent

11/06/2018, 10:03 PM
Looks that way
k

karelpeeters

11/06/2018, 10:05 PM
Then it's not actually the Sieve of Eratosthenes any more, it's more like "keep a list of primes and try all of those".
🤔 1
s

stkent

11/06/2018, 10:07 PM
I wonder if that's also true for the haskell implementation from the original video? I would think so... how else could one generate indefinitely
k

karelpeeters

11/06/2018, 10:10 PM
Yeah I'd say so, the Sieve of Eratosthenes is specifically for finding primes up to a given limit.
This is some really interesting code though!
s

stkent

11/06/2018, 10:11 PM
Makes sense. Great point!
Yeah, agreed r.e. interesting!
k

karelpeeters

11/06/2018, 10:15 PM
Haha now I'm wondering whether Haskell optimizes his
zip primes (tail primes)
.
g

gildor

11/07/2018, 12:44 AM
As I know Haskell doesn't optimize this case, except that result of this operation is lazy, but still this will generate 2 sequences of primes
👍 1
k

karelpeeters

11/07/2018, 12:51 AM
That too bad, seems like such an easy thing to do (use something
zipWithNext
-like).
n

Nikky

11/07/2018, 1:15 AM
is it possible to have a infinite list of numbers and remove numbers without creating new objects ?
k

karelpeeters

11/07/2018, 1:15 AM
Well how are you going to remember what numbers to remove?
n

Nikky

11/07/2018, 1:16 AM
i guess that needs to be stored
k

karelpeeters

11/07/2018, 1:16 AM
In a new object?
n

Nikky

11/07/2018, 1:17 AM
in mutable state i nthat sequence i guess
ahh well you cannot remoe all numbers because those are also infinite
damn
i guess you could make a datastructure keeping track of previous primes and doing
% p == 0
but thats a whole different thing then
k

karelpeeters

11/07/2018, 1:21 AM
Yeah and that's basically what's already happening in this code, just less efficient. It also stops being a nice example of sequences then 😕
e

elizarov

11/07/2018, 4:11 AM
It is a known fact that there is no way to implement the actual sieve of eratosphenes using functional immutable data structures. Mutable data structure (array) is critical for its performance.
It is a prime example of why a programming language actually needs to have mutability for performance.
Also, the original code was not lazy not because of plus, but because of eager recursive call to sieve(...) function.
❤️ 1
👍 3