Dex-chan lover
- Joined
- Jan 16, 2020
- Messages
- 174
Code:
primes = 2 : filter (null . tail . primeFactors) [3,5..]
primeFactors n = factor n primes
where
factor n (head:tail)
| head*head > n = [n]
| n `mod` head == 0 = head : factor (n `div` head) (head:tail)
| otherwise = factor n tail
main :: IO ()
main = print (primeFactors 9)This code is the prime example of how I like Haskell, and how it's cool when you finally understand
Different from the majority of languages, we don't start reading line by line, since Haskell is lazy evaluated, values are only computed when needed
The first thing that happens is we ask the code to print the function of primeFactors 9, we go to primeFactors and execute the function factor with the arguments of n and primes. At first, we don't try to know what primes is, since we don't need it right now.
The
where keyword is used for the declaration of local variables and functions, factor being one of themThe function
factor receives n(in this case 9) and (head:tail) what does this mean? It's pattern matching. (head:tail) is a single argument, that receives the primes, and divides it into head (the first element of the array) and tail (all elements except the first one)The
I are guards, like switch cases in other languages, here we declare three situations, and the value returned by the function in each case. The first case we see if head * head is bigger than n, and only now we actually need to know what head is, and to know what head is we need to know primes is. However, we only need to know the first element of primes, and both during development and runtime, it's easy to see that the first element will always be 2, so we don't need to worry about the other stuff (for now).Okay, the first guard didn't work, let's go to the second. Here
mod is the modulo function, like % in other The last guard is the easiest, it's the default one. We do a recursive call, now with the tail of primes instead of all primes, and again, we don't need to know primes or the tail of primes is for now
Okay, let's go direct to the guards, and now we need to know what the head of this new set of primes is, but it's not as clear as before.
We see the operand
:, what it does here is create a new array, with the left value being the head, and the right value being the tail of the array, like + in other languages, very simple.Let's go to primes, now that we need to know the value of the new head. We ignore the two (it was discarded in the recursive call), and go to this weird piece of code.
Code:
filter (null . tail . primeFactors) [3,5..]To understand it we need to know that different from other languages, Haskell doesn't force us to use parenthesis when passing arguments, only when we want to mix multiple values in one argument. So, filter has two arguments
(null . tail . primeFactors) and [3,5..]filter, as its name implies, is a function that receives one function(let's call this function "applier"), and an array. It traverses the array linearly, always doing
applier n where n is the current value. If this function call returns True, it puts n in a new array, if it returns False, it does not.In Haskell, due to its lazy loading, we can create (theoretical) infinite lists, we can even choose which value we start with, and the step for each value. In [3,5..] we mean, "start with the value of 3, and keep ading 2 (5 - 3), forever", so the array of filter is all odd numbers, starting with 3.
Now we only need to deal with the applier,
null . tail . primeFactors is syntactic sugar for null(tail(primeFactors), so for each n in the array we are doing
Code:
null(tail(primeFactors(n))Let's start with from the left, and go to the right. The first function
primeFactors we already know what is, it returns the list of all prime factors of a number. tail. and null are even simpler, tail returns the tail of an array(duh), and null checks if an array is empty, if it is, it returns True, otherwise it returns false.Remembering that we only need to know the head of primes, let's execute this code for the first element of [3,5..] 3. primeFactors 3 will return [3], since it will pass on the first guard. Now we check the tail of [3], it's []. Since [] is an empty list, null returns True, therefore we know that 3 is indeed a prime.
Mathematically (my weak point lol) it's clear, a prime number only has a single prime factor (besides 1 which we ignore on the array primes), itself. And we since we will be executing recursively, getting head by head rather than trying to get the complete array, we can always discover the list of primes factors of all numbers lower than our n, that was called in the first function call
Okay, let's go back to the first guard on factor 9 [3,5..], now it's easy-peasy, 3 * 3, is no bigger than 9. Let's go the second, 9 / 3 = 3, so no remainder, this guard is the correct one. We get the head(3), and append to it factor 3 [2,3,..], we know this is 3, therefore, we know now that factor 9[3,5..] is = [3,3]
And we also know that, factor 9 [2,3..] = factor 9 [3,5..] (we declared this on the first call of factor).
And now, finally, we know the value we want, and can print it, it's [3,3].
While to understand this code is probably more difficult for someone with only experience in imperative languages, it has so many interesting features that I think it's worth learning. Infinite lists, recursive calls, list comprehensions, are all key components of Haskell and other functional languages. And we didn't even touch others of it's core features, typeclasses, monads, polymorphic types.
I wanted to write this, both to learn more about Haskell, and because I really wanted to share this stuff with someone
(although like tony said the lazy evaluation is kind of scary since it is unlike anything I have ever seen before)
