I m trying to build a Kotlin version of the lazy prime numbe

Question

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 amp t=10m55s> I ended up here ``` fun sieve remainderSequence Sequence lt Int gt = generateSequence 2 it + 1 Sequence lt Int gt 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 · Answer

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

stkent · Answer

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

stkent · Answer

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

Nikky · Answer

can you show the fixed code

stkent · Answer

Sure

Nikky · Answer

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

stkent · Answer

``` fun sieve remainderSequence Sequence lt Int gt = generateSequence 2 it + 1 Sequence lt Int gt val newPrime = remainderSequence first val newRemainderSequence = remainderSequence filterNot it newPrime == 0 return sequence yield newPrime yieldAll sieve newRemainderSequence ```

Nikky · Answer

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

Nikky · Answer

thx

stkent · Answer

No problem slightly smiling face

karelpeeters · Answer

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

stkent · Answer

Looks that way

karelpeeters · Answer

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 · Answer

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 · Answer

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

karelpeeters · Answer

This is some really interesting code though

stkent · Answer

Makes sense Great point

stkent · Answer

Yeah agreed r e interesting

karelpeeters · Answer

Haha now I m wondering whether Haskell optimizes his `zip primes tail primes `

gildor · Answer

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 · Answer

That too bad seems like such an easy thing to do use something `zipWithNext` like

Nikky · Answer

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

karelpeeters · Answer

Well how are you going to remember what numbers to remove

Nikky · Answer

i guess that needs to be stored

karelpeeters · Answer

In a new object

Nikky · Answer

in mutable state i nthat sequence i guess

Nikky · Answer

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

Nikky · Answer

damn

Nikky · Answer

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

karelpeeters · Answer

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 confused

elizarov · Answer

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 · Answer

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

elizarov · Answer

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