So I decided to begin learning Haskell. Like many functional programming languages, it isn’t used very often in the software development industry compared to its imperative cousins. However, I still believe it’s good to learn a functional programming language because you get to solve problems from a different perspective. All the problems I solved with Haskell I could’ve also used C++ or C# or anything really but by using a functional language instead, it meant that I had to approach the problems in a different manner and I believe it has strengthened my ability to problem solving since I now have several paths to take and can choose the easier path. Some of the problems were much easier to solve in functional programming than in imperative programming and vice versa. If I had only learned one of the types, I would have fewer options to reach the end goal.
There are other reasons why Haskell is useful but I’ll leave you to see the benefits of it by pointing you to the same learning resource I used — Learn You A Haskell For Great Good!
To test out what I had learned in Haskell I decided to do some of the problems listed on two websites:
I spent most of the time in Project Euler and decided to see how many of the problems I could solve using Haskell in the 2 days I had free. I got through a handful of the 99 Haskell problems before getting a little bored and moved on to complete around 20 of the Project Euler problems.
(note: If you’re a Haskell pro reading this then you might look at some of this code and think it’s terrible. Some of it definitely is(!) but realise I only started learning recently so there will be plenty of times that I miss a feature of Haskell that could’ve greatly helped or some in-built function that I have unknowingly re-invented myself. I also haven’t yet entered the world of monads either as I’m not entirely sure I will need it for my purposes).
So for my “proof” that I do indeed know Haskell, I will show and briefly describe my solutions for the problems on Project Euler. There are some I aren’t happy with performance wise since I genuinely struggled to think about how to solve the problem recursively (a commonly required skill for Haskell, which lacks sequence and iteration constructs) but none-the-less they all gave me the correct answers in just a few lines of code.
In the end I completed around 20 or so problems in the 2 days but that would take up too much space in one post so it’ll be split up into several posts, maybe 3.
Problem 1 – Find all sum of all multiples of 3 or 5 below 1000
sum [x | x <- [1..999], x `mod` 3 == 0 || x `mod` 5 == 0]
Nothing much to say here, generate a range from 1 to 999, grab the ones that satisfy the predicate (if a multiple of 3, then integer division by 3 will leave a remainder of 0, similarly for 5) then sum up all the elements in the resultant list.
Problem 2 – Find the sum of the even valued terms in the sequence of Fibonacci numbers below 4,000,000
Firstly, some people start the sequence as 0,1,1,2… whereas others start 1,1,2… but Project Euler wanted it to start as 1,2,3,5… which I’ve never seen before but oh well. Firstly, a function to generate the Fibonacci sequence:
fibonacci :: Int -> Int
fibonacci 0 = 1
fibonacci 1 = 2
fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)
It uses pattern matching to grab the non-recursive cases. The answer is then found simply with:
sum $ filter even $ takeWhile (<4000000) $ map fibonacci [0..]
It can be read as: keep generating Fibonacci numbers and add to a list until you finally reach one that is at least 4,000,000. Then grab only the even ones and then sum all these even terms up. The problem with this is that if I ask for fibonacci 10, say, and then ask for fibonacci 11, it will recalculate fibonacci 10. I need to store this in some form of cache like so:
let fibonacci = 1 : 2 : zipWith (+) fibonacci (tail fibonacci)
Haskell’s laziness means I can have infinite lists like this with no problem as it’s more of a “promise” that it could produce an infinite list at some point in the future. The solution then simplifies to:
sum $ filter even $ takeWhile (<4000000) $ fibonacci
Problem 3 – What is the largest prime factor of the number 600851475143?
The first problem is finding out if a number n is prime which I did by generating all the greatest common divisors between 1 and the square root of n. If all the greatest common divisors are equal to 1 or n, then n is prime. This was done with the following functions:
greatestCommonDivisor :: Integer -> Integer -> Integer
greatestCommonDivisor a 0 = a
greatestCommonDivisor a b = greatestCommonDivisor b (a `mod` b)
isPrime :: Integer -> Bool
isPrime x | x <= 1 = error "Please enter a number greater than one"
isPrime x = let listOfDivisors = map (greatestCommonDivisor x) [1..ceiling (sqrt (fromIntegral x)) :: Integer]
in all (\a -> a == 1 || a == x) listOfDivisors
And finally to generate multiple primes and test whether they are factors of n:
primesR :: Integer -> Integer -> [Integer]
primesR a b = filter isPrime [a..b]
primeFactors :: Integer -> [Integer]
primeFactors n = let r = ceiling (sqrt (fromIntegral n)) :: Integer
in filter (/=1) (map (greatestCommonDivisor n) (primesR 2 r))
The largest one, is simply the last one so the answer becomes:
last $ primeFactors 600851475143
This however is very slow, probably because of the fact that the method of checking if a number is prime is not done the best way but none-the-less it generates the correct answer. So I came up with a faster way that orders the expensive computations to be done as late as possible:
maximum $ filter isPrime $ filter (/=1) (map (greatestCommonDivisor 600851475143 ) [1..ceiling (sqrt (fromIntegral 600851475143)) :: Integer])
Problem 4 – Find the largest palindrome made from the product of two 3-digit numbers
Firstly, a function to detect if something is a palindrome:
isPalindrome :: (Eq a) => [a] -> Bool
isPalindrome x = x == reverse x
If you reverse the list and the order of those elements equals the ordering of the initial list, it’s a palindrome. Problem is, this works on lists not numbers so you use the built in show function to turn a number into its string equivalent which in turn is seen as a list of characters. As it’s a list, we can now pass it to the above function.
maximum [ read x :: Integer | x <- filter isPalindrome [ show (x * y) | x <- [100..999], y <- [100..999] ] ]
So when read from right to left, generate all the product combinations for 3 digit numbers, use show to create the string equivalent, then grab those strings that are palindromes and re-extract the number from the string (the read function is sort of the opposite of show). We are no left with a list of palindromic numbers and pass it to the maximum function to find the largest in this list.
Since x * y is equal to y * x we can shorten the y range to make the function faster:
maximum [ read x :: Integer | x <- filter isPalindrome [ show (x * y) | x <- [100..999], y <- [100..x] ] ]
Problem 5 – What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
This problem comes with the example:
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
This can be shown to be true with the following code and its output:
*Main> map (mod 2520) [1..10]
*Main> map (mod 2520) [1..20]
We basically need to find a number n such that map (mod n) [1..20] produces all zeroes.
This was my first attempt:
(fst $ last $ takeWhile (\(n, r) -> r == False) ([ (x, all (==0) (map (mod x) [1..20])) | x <- [1..] ])) + 1
But it’s laughably slow so I decided to look for another way and did some research into the modulus. It turns out that we can also find this answer by calculating the lowest common multiple between 20 and the lowest common multiple of all the numbers before it. So it’s very similar to how the factorial is calculated in that 5! = 5 * 4! = 5 * 4 * 3! and so on all the way down. It just so happens that there is a built in method that calculates the lowest common multiple, lcm. The next part is to recursively call the function on the entire list to reduce it to a single value…this is a fold! and there’s also a bunch of fold functions built in too so this problem is solved very easily with Haskell:
foldl (lcm) 1 [1..20]
Problem 6 – Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum
This one is really easy!
let sumOfSquares = sum $ map (^2) [1..100]; squareOfSum = sum [1..100] ^ 2
in squareOfSum - sumOfSquares
One map to generate all the squares, and then sum it and another map to generate the sum and then square it and finally a subtraction between the two.
Problem 7 – What is the 10 001st prime number?
Using the isPrime function from an earlier problem, I made a function that generates an infinite list of primes:
primesS :: Integer -> [Integer]
primesS a = filter isPrime [a..]
Then you simply assign a number to each prime and stop when you reach the 10001st one:
let primes = primesS 2
snd $ last $ zip [1..10001] primes
Problem 8 – Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?
Making the number a string (char list) is easiest to allow us to go through the digits one at a time. Then using the Data.Char digitToInt function, we turn the char containing a number into an actual number and sum up every 13 numbers.
productNFromString :: [Char] -> Int -> Int -> Int -> Int
productNFromString s x l si
| si >= l = 1
| si < l = digitToInt (s !! x) * productNFromString s (x + 1) l (si + 1)
maximumProductNFromString :: [Char] -> Int -> Int
maximumProductNFromString ns l = maximum [ productNFromString ns x l 0 | x <- [0..(length ns - l)]]
s is the string form of the large number, x is the index to start from, l is the limit to how far ahead of x we need to go (so for example, if x was 10 and l was 4 then we need to use 10, 11, 12, 13 as indices but not any further) and si is just an internal counter keeping track of how far ahead of l we have gone so far (so we know when to stop).
The 1000 digit number itself is well, very large, so I won’t paste it here just grab it from Project Euler!
Problem 9 – There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.
Since the condition a + b + c = 1000 is there, then we can immediately limit the search for values of a b and c between 1 and 1000.
isPythaTriplet :: Int -> Int -> Int -> Bool
isPythaTriplet a b c = a^2 + b^2 == c^2
filter (\(a,b,c) -> isPythaTriplet a b c) [ (a, b, c) | a <- [1..1000], b <- [1..1000], c <- [1..1000] ]
The above generates a list of all valid triangles with a b c values between 1 and 1000.
filter (\(a,b,c) -> a + b + c == 1000) $ filter (\(a,b,c) -> isPythaTriplet a b c) [ (a, b, c) | a <- [1..1000], b <- [1..1000], c <- [1..1000] ]
The above filters the list to include only the ones where a + b + c == 1000
Since we know there is only one possible solution, the resultant list should have only one element so we can use the head function to get it
let answer = head $ filter (\(a,b,c) -> a + b + c == 1000) $ filter (\(a,b,c) -> isPythaTriplet a b c) [ (a, b, c) | a <- [1..1000], b <- [1..1000], c <- [1..1000] ]
*Main> (\(a,b,c) -> a * b * c) answer
A better solution may have been to filter out all the triplets that sum up to 1000, then filter out the ones that are triangles after wards since the pythatriplet test is the most expensive part of the expression by far:
filter (\(a,b,c) -> isPythaTriplet a b c) $ filter (\(a,b,c) -> a + b + c == 1000) [ (a, b, c) | a <- [1..1000], b <- [1..1000], c <- [1..1000] ]
Another optimization is to realise that 3 4 5 and 4 3 5 are the same, the order doesn’t matter for the first two, so we can just take the first ordering of 3 4 5 and ignore the latter one. Also, the last number is always larger than the first two so with these two constraints in place, the first is always smaller than the second which is always smaller than the third. This means instead of having “a” go between 1 and 1000 (and similarly for b) we can have:
filter (\(a,b,c) -> isPythaTriplet a b c) $ filter (\(a,b,c) -> a + b + c == 1000) [ (a, b, c) | c <- [1..1000], b <- [1..c], a <- [1..b] ]
With the optimizations shown in bold in the texas ranges.
Another optimization is that C only needs to be at most 500 because there is no a and b such that a^2 + b^2 == 500^2 AND a + b + 500 <= 1000
In terms of what it’s doing, there isn’t much more to optimize. However, because of the constant tupling and un-tupling of data, we can certainly optimize how it’s doing it. By getting rid of the tuples altogether! And also replacing the (\(a,b,c) -> a * b * c) lambda with the built in product function and moving the filters inside the list comprehension itself so we’re reducing the number of times the list data gets copied:
*Main> product $ head $ [ [a, b, c] | c <- [1..500], b <- [1..c], a <- [1..b], a + b + c == 1000, isPythaTriplet a b c ]
I then thought of another slight optimization. There’s no point in iterating through a texas range for A. If we know what a + b + c == 1000 and we know the values of b and c, we can rearrange the equation to get a == 1000 – b – c and since we know the values of b and c, we can get the exact value for a:
product $ head $ [ [a, b, c] | c <- [1..500], b <- [1..c], a <- [1000-b-c], isPythaTriplet a b c ]
which is much much faster than any of the above attempts.
Stay tuned for parts 2 and 3 coming up.