primes.nix

let

rec' = hd: tl: self: args: { value = hd args; next = self (tl args); };

step = rec' ({ step, value }: value) ({ step, value }: { inherit step; value = value + step; });

nat2 = lib.fix step { step = 1; value = 2; };

subtract_sorted = self: xs: ys: 
  if xs.value < ys.value then
    { inherit (xs) value; next = self (xs.next) ys; }
  else if xs.value > ys.value then
    { inherit (xs) value; next = self (xs.next) (ys.next); }
  else
    self (xs.next) (ys.next);

sieve = p: lib.fix step { value = p * p; step = p; };

prime_gen = self: candidates:
  let
    inherit (candidates) value;
  in
    { inherit value; next = self (lib.fix subtract_sorted (candidates.next) (sieve value)); };

prime = lib.fix prime_gen nat2;

in
prime