The Infinite 'Lazy List' of Primes in ML

 In ML (or other functional languages, such as haskell), a 'lazy list' is a list data structure where there is a delay in accessing the next element - we can specify how to compute it, but allow it's execution to be at some later time. We need to apply a special value to it to get the next value (() of type unit in ML). The ML datatype is below
                datatype 'a seq = Nil
                                | Cons of 'a * (unit -> 'a seq);
The function below, when given an integer $k$, returns the lazy list containing $k,k+1,...$ 
                fun from k = Cons(k, fn()=> from(k+1));
We define the required lazy list functions: 
                fun get (0, _) = []
                  | get (_, Nil) = []
                  | get (n, Cons(x,xf)) = x :: get (n-1, xf());
                  
                fun head (Cons(x,_)) = x;
                
                fun nth (1,x) = head(x)
                  | nth (n,Cons(x,xf)) = nth(n-1,xf());
The function below ('drop multiples') modifies the given list so that it contains no multiples of the given integer. 
                fun dm(n,Cons(x,xf)) = if x mod n = 0 then dm(n,xf()) else Cons(x,fn ()=>dm(n,xf()));
Since a prime is a number with the property that it has no divisors except 1 and itself, we can define the primes lazy list as 
                val primes = let 
                               fun primesgen (Cons(x,xf)) = Cons(x,fn () => primesgen(dm(x,xf())));
                             in
                               primesgen (from 2)
                             end;
Now go and tell a mathematician that you have an infinite list of prime numbers on your computer!