I'm trying to build a Kotlin version of the lazy p...

# announcements

[stkent]

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?

[elizarov]

You should put all code inside sequence { } and instead plus use yieldAll

[stkent]

Awesome, that works! What is it about plus that prevents this from working the same way as yieldAll?

[stkent]

plus was marked as 'intermediate' so I thought the evaluation would still be lazy?

[Nikky]

can you show the fixed code ?

[stkent]

Sure!

[Nikky]

i think this would be nice demo for my friends to expose them to a bit more than plain old java in school

[stkent]

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))
    }
}

[Nikky]

since they recently mentioned doing exactly this sieve of Eratosthenes using arrays

[Nikky]

thx

[stkent]

No problem 🙂

[karelpeeters]

Huh. So where's the actual memory usage now? `FilteringSequence`s that just keep nesting?

[stkent]

Looks that way

[karelpeeters]

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".

[stkent]

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

[karelpeeters]

Yeah I'd say so, the Sieve of Eratosthenes is specifically for finding primes up to a given limit.

[karelpeeters]

This is some really interesting code though!

[stkent]

Makes sense. Great point!

[stkent]

Yeah, agreed r.e. interesting!

[karelpeeters]

Haha now I'm wondering whether Haskell optimizes his zip primes (tail primes).

[gildor]

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

[karelpeeters]

That too bad, seems like such an easy thing to do (use something zipWithNext-like).

[Nikky]

is it possible to have a infinite list of numbers and remove numbers without creating new objects ?

[karelpeeters]

Well how are you going to remember what numbers to remove?

[Nikky]

i guess that needs to be stored

[karelpeeters]

In a new object?

[Nikky]

in mutable state i nthat sequence i guess

[Nikky]

ahh well you cannot remoe all numbers because those are also infinite

[Nikky]

damn

[Nikky]

i guess you could make a datastructure keeping track of previous primes and doing % p == 0 but thats a whole different thing then

[karelpeeters]

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 😕

[elizarov]

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.

[elizarov]

It is a prime example of why a programming language actually needs to have mutability for performance.

[elizarov]

Also, the original code was not lazy not because of plus, but because of eager recursive call to sieve(...) function.