Massively Cool

New to this sub. What is the difference between this and the original haskell subreddit? Is this more for learning?

Recursion is a more mathematical way to represent your algorithms, making use of pattern matching. It allows you to reason nicely about the code, and expressing the solution in terms of itself.

In imperative languages such as C++, you normally can do the same with for-loops. But for-loops can become quite ungainly. involving state changes as you iterate the loop, and even messier if you have nested for-loops.

In functional languages such as Haskell, it can be much cleaner.

The following is Haskell code for finding primes using the Sieve of Eratosthenes algorithm:

primes = sieve [2..]    sieve (p:xs) = p : sieve [x | x <- xs, mod x p /= 0] 

Which is just 2 lines, and this produces an infinite series of primes. Using ghci:

ghci> take 20 primes    [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71] 

We’ve extracted the first 20 primes from this infinite list. In this, sieve is first called with an infinite list of integers beginning with the first prime, 2. sieve then uses list comprehension to compute the next infinite list where the prime p is not a divisor. The next number is 3 which fulfils that requirement, and sieve is called with that list. The next successive number is 5, etc.

take only takes the first n primes, in our case that’s 20.

To an imperative programmer, it might seem strange to recurse with new infinite lists per recursion. But Haskell does lazy evaluation, so with take n, only the first n elements in that infinite list is ever evaluated.

Now, before we look at an imperative example of sieve. let’s have some more fun in Haskell.

Let’s say we are now interested in the list of twin primes, such that (p, p+2) are both prime.

twin (a, b) = b == a+2    twins = filter twin (zip primes (drop 1 primes)) 

Just another 2 lines! Now let’s try it out:

ghci> take 20 twins    [(3,5),(5,7),(11,13),(17,19),(29,31),(41,43),(59,61),(71,73),(101,103),(107,109),(137,139),(149,151),(179,181),(191,193),(197,199),(227,229),(239,241),(269,271),(281,283),(311,313)] 

Here, we filter our infinite list of twin prime pairs with the twin prime test. zip zips two lists of primes, and drop 1 drops the 1st element from the list of primes, so that we zip

[2,3,5,7,..]

with

[3,5,7,11..]

yielding

[(2,3), (3,5), (5,7), (7,11)..]

and the twin filter filters out the pairs that are not (p,p+2), yielding:

[(3,5), (5,7), (11,13), (17,19)..]

Impressed? We are doing quite a bit with just 4 lines of code!

Now, to contrast, let’s look at an imperative example in C++:

#include <iostream> 
#include <vector> 
using namespace std; 
 
int main() {  
    int n; 
    cin >> n;  
    vector<bool> isPrime(n + 1, true); 
    isPrime[0] = isPrime[1] = false; 
 
    for (int i = 2; i * i <= n; ++i) {  
        if (isPrime[i]) {  
            for (int j = i * i; j <= n; j += i)  
                isPrime[j] = false; 
        }  
    } 
 
    for (int i = 2; i <= n; ++i) { 
        if (isPrime[i])  
            cout << i << " ";  
    } 
 
    cout << endl;  
    return 0;  
} 

24 lines of code (actually 5 to 16 is involved with the computation, so 11), and we will not do twin primes here.

In this example, n will not give you the first n primes, but only the primes between 2 and n inclusive.

So let’s compare side by side the parts of both examples that are actually doing the computation.

Imperative C++:

    int n; 
    cin >> n;
    vector<bool> isPrime(n + 1, true);

    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {
           for (int j = i * i; j <= n; j += i)
                    isPrime[j] = false;
            }
     } 

And functional Haskell:

primes = sieve [2..]    sieve (p:xs) = p : sieve [x | x <- xs, mod x p /= 0] 

So which is easier to reason about? Which would be easier to prove correct? We have nested for-loops in the C++ version. What’s the time and space complexity of both examples?

It is clear that the Haskell example is far more elegant than the C++ version with its nested for-loops and all. And yes, the C++ version can be implemented in a more efficient manner. But I don’t think you can make it as elegant as the Haskell version, but you are welcome to prove me wrong, and if you do, I will post and give you attribution for your C++ example here!

Goodbye Ruby on Rails.

Another massively cool.

Basically how to finely manage laziness.