Sieve_Original.enso

from Standard.Base import Any, Meta, Integer, True, False, Nothing

type Gen
    Generator n:Integer

    next : Gen
    next self = Gen.Generator self.n+1

natural : Gen
natural =
    gen n = Gen.Generator n
    gen 2

type Filter
    Empty
    Item n:Integer next
    Head first:Filter set_last:Filter->Nothing

    acceptAndAdd : Integer
    acceptAndAdd self n =
        iterate f = case f of
            Filter.Item p next -> if n % p == 0 then False else
                if p * p > n then True else @Tail_Call iterate next
            Filter.Empty -> True

        appendN head set_last =
            pair = Meta.atom_with_hole (h -> Filter.Item n h)
            newLast = pair.value
            set_last newLast
            [True, Filter.Head head.first pair.fill]

        case self of
            Filter.Empty ->
                pair = Meta.atom_with_hole (h -> Filter.Item n h)
                [True, Filter.Head pair.value pair.fill]
            Filter.Head _ _ -> if iterate self.first then appendN self self.set_last else [False, Nothing]

type Primes
    Alg generator filter

Primes.next self = case self of
    Primes.Alg g f ->
        found_new = f.acceptAndAdd g.n
        if found_new.first then Primes.Alg g.next found_new.last else
            new_primes = Primes.Alg g.next f
            @Tail_Call new_primes.next

Primes.last_prime self = case self of
    Primes.Alg g _ -> g.n - 1


compute_nth_prime n =
    loop p n = if n == 0 then p else
        pn = p.next
        @Tail_Call loop pn n-1
    p = Primes.Alg natural Filter.Empty
    loop p n . last_prime