Continuing from the previous one, here are my solutions to problems 6-10. Same warning applies – they are unusually long for a Haskell program and as usual take them with a grain of salt.
Project Euler 6 in Haskell
ssdiff :: Int -> Int ssdiff n = (sum [1..n] ^ 2) - (sum $ map (^2) [1..n]) main = do print $ ssdiff 10 print $ ssdiff 100
Project Euler 7 in Haskell
import Data.Numbers.Primes nthprime :: Int -> Int nthprime n = primes !! (n-1) main = do print $ nthprime 6 print $ nthprime 10001
Project Euler 8 in Haskell
import Data.Char import Data.List minLen :: Int -> [a] -> Bool minLen n xs = not $ null (drop n xs) nibbles :: Int -> [a] -> [[a]] nibbles n xs = map (take n) $ filter (minLen n) $ tails xs prod :: String -> Int prod s = product $ map digitToInt s maxProd :: String -> Int -> Int maxProd s n = maximum $ map prod (nibbles n s) main :: IO () main = do txt <- readFile "src/Euler/euler8.txt" numTxt <- return $ concat $ lines txt print $ maxProd numTxt 4 print $ maxProd numTxt 13
Project Euler 9 in Haskell
pythTrip :: Int -> Int pythTrip n = head [a * b * c | a <- [1..n - 2] , b <- [a + 1..n - 2] , let c = n - a - b , c > b , a ^ 2 + b ^ 2 == c ^ 2] main :: IO () main = do print $ pythTrip 1000
Project Euler 10 in Haskell
This one was interesting. Using the Data.Numbers.Primes package, it’s very easy and very fast:
import qualified Data.Numbers.Primes as P sumOfPrimes :: Int -> Integer sumOfPrimes n = (sum . map toInteger . takeWhile (< n)) P.primes main :: IO () main = do print $ sumOfPrimes 10 print $ sumOfPrimes 2000000
However, I was intrigued how to do Sieve of Eratosthenes in Haskell. Here’s what I came up with:
import qualified Data.Vector.Unboxed as UV sieve :: Int -> UV.Vector Bool sieve m = let s = UV.replicate (1 + m) True sqm = (floor . sqrt . fromIntegral) m update v n | v UV.! n == False = v | otherwise = UV.update v (UV.zip xs ys) where sqn = n * n xs = UV.enumFromStepN sqn n (1 + (m - sqn) `div` n) ys = UV.replicate (UV.length xs) False sievep v n | n <= sqm = sievep (update v n) (n + 1) | otherwise = v in sievep s 2 primes :: Int -> [Int] primes m = (UV.toList . UV.drop 2 . UV.map fst . UV.filter ((== True) . snd) . UV.zip (UV.enumFromN 0 (1 + m)) . sieve) m sumOfPrimes :: Int -> Integer sumOfPrimes = sum . map toInteger . primes main :: IO () main = do print $ sumOfPrimes 10 print $ sumOfPrimes 2000000
I must say I was a bit surprised how the process of writing turned out to be different. First, I used Vectors and Arrays package provided much confusion here. Not sure if I’m right, but looks like Vectors package is newer. Some things such as DiffArray turned out to be unsuccessful experiments, for example. Second, I found it quite un-Haskelly, given the solution is non-lazy and bounded.
I guess the number of different solutions and papers (some relatively new to that point) that I found, especially on the main Haskell Wiki page says a lot:
- https://www.haskell.org/haskellwiki/Prime_numbers
- http://rosettacode.org/wiki/Sieve_of_Eratosthenes
- http://lambda-the-ultimate.org/node/3127
- http://stackoverflow.com/questions/11768958/prime-sieve-in-haskell
I guess I’ll just go with the built-in for now.