I just came across a great read called “The one time I thought I understood recursion”, which talked about a developer’s first steps with Haskell.
He’s doing the classic “find the n-th prime” algorithm, that has a typical recursive solution. It includes a snippet that solves the problem in a way that’s just as beautiful as it is impossible to understand for me right now, without any Haskell knowledge.
So I’ve decided to (finally) start my Journey into Haskell by understanding how that snippet works. Please note that I know nothing of Haskell as of now! So I’m going to be learning as I go through the snippet.
Every thing written here may be (and very likely is) wrong!
nth :: Integral a => Int -> Maybe a
nth 0 = Nothing
nth x = Just (last $ primes x)
primes :: Integral a => Int -> [a]
primes n = take n $ sieve [2..]
where sieve (p:xs) = p : sieve [x | x <- xs, x `rem` p > 0]
sieve [] = []
I’ll start by trying to understand what each line does:
nth :: Integral a => Int -> Maybe a
At a glance :: seems to be declaring a variable, which will be a function that takes an Int, and maybe? returns an Int. The maybe seems to be similar to Java’s Optional. But why the Integral a then?
Reading up on it this turns out to be way more interesting than I thought! Integral a is the argument to the function, followed by a list of potential return types. This means that in some cases the function will return an Int (the nth prime), and in other cases it might return the same as the input.
nth 0 = Nothing
Seems easy, when calling nth with 0 as the argument, we return Nothing. From the docs and SO, Nothing represents a lack of value for a Maybe XXX type. Hence the Maybe a above.
nth x = Just (last $ primes x)
After a bit of help from SO, I think I get it: For any other argument x, Just is a constructor for Maybe which “asserts” that x does have a value (or that the function on its right will not return Nothing, I’m not fully sure now), then runs the functions in the parenthesis.
last is obvious, it returns the last element on a list.
$ is not so much. It required some additional reading to understand that it’s essentially sugar for more parenthesis, so AFAIK, the following two lines would do the same:
nth x = Just (last $ primes x)
nth x = Just (last (primes x))
The article goes to pretty scary deep places regarding the use of the $ sign, but I’m gonna leave that for future me :) For now I get what it’s doing in this context and that’s going to be enough.
The last thing is to call the function primes with the argument x, which seems to be defined later on (Apparently because Haskell does lazy evaluation you can define functions in any order). I assume that primes will be a function that takes one integer and returns a list of integers (primes) up to that one.
primes :: Integral a => Int -> [a]
The type definition for primes confirms the assumption, let’s move on to the body (I’ll show it complete first, then break it down by lines)
primes n = take n $ sieve [2..]
where sieve (p:xs) = p : sieve [x | x <- xs, x `rem` p > 0]
sieve [] = []
Time to roll my sleeves up, this looks like a mess! Where do I start…?
primes n = take n $ sieve [2..]
So primes is a function with one argument n, that returns take n $ sieve [2..]. Let’s see what that does:
take is a built-in function that takes two arguments, an integer (N) and a list, and returns the first N elements of the list (or less if the list is not long enough).
It’s being called with n (the argument from primes, which was actually the nth integer from the start), and $ sieve [2..] which as I have learnt should become the return value of sieve [2..].
I’m still not sure whether sieve is built-in or defined below where it says where sieve (p:xs) =, so I’ll finish this line first. [] is an operator that creates a list (or maybe I should call it sugar for the List constructor?) and 2.. means all integers starting from 2. Ok, getting there!
Now we move on to the definition of sieve:
where sieve (p:xs) = p : sieve [x | x <- xs, x `rem` p > 0]
where is a way to define functions based on their inputs, quite similar to what happened earlier, and after reading some documentation I’m still not 100% sure about when it’s best to be used, but I think I get what it does.
Something awesome that I’m realising now is the “lazy evaluation” part of Haskell. If you wrote this code in Java for example it would simply never end because we’re calling sieve with an infinite list! But thanks to Haskell’s lazy evaluation sieve [2..] doesn’t get evaluated when defined, but when it’s return value is needed. So because take n needs the first n elements of the list returned by sieve [2..], it will only evaluate until then. I’m blown away!
The next bit that looks odd is p:xs, my guess is that this represents an argument of type list, where the start is stored in p and the end in xs? but the list was unbounded (defined as 2..) so surely I’m missing something here (I was, I figured it out by the next paragraph). Time to read.
Ok, it turns out that p:xs is a fairly standard convention, although the typical way of writing it is x:xs. In Haskell it’s common to end list variables with an s, and use a single letter for single values. The fact that they chose p instead of x is an indication that it’s value is special - it’s a prime number (well, it should be).
After reading some more, I understand that p:xs is a pattern (and patterns look AWESOME in Haskell!), which means that p is the first element, and xs is the rest of the list. For example if you needed the first two elements and then the rest, you could write p:s:xs, where p would be the first, s the second, and xs the rest.
For example the first time sieve runs p = 2 and xs = [3, 4, 5...].
Now the return of the function: p : sieve [x | x <- xs, x `rem` p > 0].
Based on what I’ve learned so far, this is defining a new pattern that starts with p and ends in the return value of sieve [x | x <- xs, x `rem` p > 0], which should end up being a list of primes in xs.
The argument for the recursive call to sieve: x | x <- xs, x `rem` p > 0 is what’s called list comprehension, or in other words, get a subset of the original list where each element satisfies some conditions. The syntax seems to be {return_var} | {return_var} from {list}, {condition 1}[, {condition 2}, ...].
So in this case it says “list of all x from xs such that x `rem` p > 0. And without reading up on this, I’m assuming this says where the remainder of dividing xby p is greater than 0? (Yes, that’s it)
And the last line:
sieve [] = []
It simply returns an empty list when sieve is called with an empty list.
Recap
Ok so now that I (mostly) get the syntax it’s time to have a look at the algorithm again and see if I can make sense of it.
nth :: Integral a => Int -> Maybe a
nth 0 = Nothing
nth x = Just (last $ primes x)
primes :: Integral a => Int -> [a]
primes n = take n $ sieve [2..]
where sieve (p:xs) = p : sieve [x | x <- xs, x `rem` p > 0]
sieve [] = []
Our nth function returns the largest prime lower or equals to an integer we pass.
If we pass 0, we get nothing.
If we pass any other number, we’ll first calculate all primes up until that number and then return the last one. (Note: I just caught myself thinking in “non-lazy” style again! the sentence should actually say “we’ll calculate primes as we need them, up until the number specified”)
In order to calculate all primes until that number, we’ll start with a list of all integers starting by 2, and return a subset of the list starting from the next integer that is not divisible by it.
So if we call the function with 14, we’d expect the output to be 13. Let’s run through what happens:
sieve [2..]
// ------- //
return = [2]
p = 2
xs = [3..]
// ------- //
return = [2, 3]
p = 3
xs = [5, 7, 11, 13]
// ------- //
return = [2, 3, 5]
p = 5
xs = [7, 11, 13]
// ------- //
return = [2, 3, 5, 7]
p = 7
xs = [11, 13]
// ------- //
return = [2, 3, 5, 7]
p = 7
xs = [11, 13]
// ------- //
return = [2, 3, 5, 7, 11]
p = 13
xs = [] // this list would probably have some elements, but they are no longer important
return = [2, 3, 5, 7, 11, 13]
Take the last element:
Return 13
This was pretty cool! I’m now going to set up Haskell locally to start writing some code myself, so hopefully my Journey continues and I can post Part 2 at some point!