You can read about these subjects in Learn You a Haskell, chapter 8 "Making Our Own Types and Typeclasses".
We've already seen that we can write a function to generate an infinite list of numbers:
intsFrom :: Integer -> [Integer] intsFrom x = x : intsFrom (x + 1)
For example:
> take 10 (intsFrom 1) [1,2,3,4,5,6,7,8,9,10]
We can use a similar technique to generate an infinite list of Fibonacci numbers:
fibsFrom :: Integer -> Integer -> [Integer] fibsFrom i j = i : fibsFrom j (i + j)
Let's try it:
> take 15 (fibsFrom 1 1) [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610]
Notice that in each of the examples above, our function produced one list element, then called itself recursively to generate the rest of the list.
We can use a similar technique to generate an infinite list of all prime numbers using the Sieve of Eratosthenes. Let's review how the Sieve works. We start with a list of all integers from 2 onward:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 …
We accept the first of these (2) as prime, then remove all multiples of 2 from the list. We are left with
3 5 7 9 11 13 15 17 19 21 23 25 …
Now we accept the first of these (3) as prime, then remove all multiples of 3 from the list. We are left with
5 7 11 13 17 19 23 25 …
And so on.
Above, the recursive function intsFrom takes a single integer as an argument. The function fibsFrom takes two integers. Our recursive sieve function will take an infinite list as an argument. Each time it's called, it will accept the first value as prime, remove all its multiples from the list, then recurse. Here is an implementation:
primes :: [Integer] primes = sieve [2..] where sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
Let's try it:
> take 20 primes [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]
Let's revisit the function above that produced an infinite list of integers:
intsFrom :: Integer -> [Integer] intsFrom x = x : intsFrom (x + 1)
Alternativel we may produce this list using a recursive value definition. Consider an infinite list of integers starting with 1:
[1, 2, 3, 4, 5, ...]
If we add 1 to each element of the list, we get
[2, 3, 4, 5, …]
which is the same as the tail of the original list. So we may in fact define this list as 1 followed by the result of adding 1 to each element:
ints :: [Integer] ints = 1 : map (+1) ints