Euler in Haskell

.gitignore

*.exe
*.hi
*.o

10001st_prime.hs

import Data.Function.Memoize

-- Returns the next prime after n
nextPrimeInternal f n =
    let nextGuess = if n `mod` 2 == 0 || n < 2 then n + 1 else n + 2 in
    if isPrime nextGuess
    then nextGuess
    else f nextGuess

nextPrime :: Integer -> Integer
nextPrime = memoFix nextPrimeInternal

-- Tries to return prime factors, but may also return n or start
smallestFactor n start
    | start > floor (sqrt (fromIntegral n)) = n
    | n `mod` start == 0 = start
    | otherwise = smallestFactor n (nextPrime start)

-- Returns the prime factors of n
factor n =
    let primeFactor = smallestFactor n 2 in
    if primeFactor == 1
    then []
    else primeFactor : (factor (n `div` primeFactor))

-- Returns True if n is prime
isPrime n = (smallestFactor n 2) == n

-- Pretty slow, but manageable if nextPrime is memoized
main = putStrLn (show (iterate nextPrime 1 !! 10001))

divis_20.hs

-- v1 (very slow):
--find (\a -> all (\b -> a `mod` b == 0) (reverse [2..20])) [1..]

-- v2 (blazin'):
main = putStrLn (show (foldl (\a b -> a * b `div` (gcd b a)) 1 [2..20]))

factor.hs

-- Returns the next prime after n
nextPrime n =
    let nextGuess = if n `mod` 2 == 0 || n < 2 then n + 1 else n + 2 in
    if isPrime nextGuess
    then nextGuess
    else nextPrime nextGuess

-- Tries to return prime factors, but may also return n or start
smallestFactor n start
    | start > floor (sqrt (fromIntegral n)) = n
    | n `mod` start == 0 = start
    | otherwise = smallestFactor n (nextPrime start)

-- Returns the prime factors of n
factor n =
    let primeFactor = smallestFactor n 2 in
    if primeFactor == 1
    then []
    else primeFactor : (factor (n `div` primeFactor))

-- Returns True if n is prime
isPrime n = (smallestFactor n 2) == n

main = putStrLn (show (foldl max 0 (factor 600851475143)))

-- For profiling:
--main = putStrLn (show (nextPrime 10000000003))
--main = putStrLn (show (factor 600851475148))

fib.hs

import Data.Function.Memoize

-- Int = machine specific, Integer = arbitrary precision "big int"
fib :: Int -> Integer
fib =
    -- Can't tail-call optimize, memoizing instead
    let fibInternal f n
            | n == 0 || n == 1 = 1
            | otherwise = f (n - 1) + f (n - 2)
    in memoFix fibInternal

main =
    let smallFibs = takeWhile (\a -> a < 4*10^6) (map fib [1..])
        evenFibs = filter (\a -> a `mod` 2 == 0) smallFibs
    in putStrLn (show (sum evenFibs))

greatest_product.hs

import Data.Digits -- cabal install digits
import Data.List

n = 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450

dropFromEnd n xs = zipWith const xs (drop n xs) -- sneaky runtime improvement on my original implementation


main =
    let products = map (foldl (*) 1) $ dropFromEnd 5 $ map (take 5) (tails (digits 10 n))
    in putStrLn (show (foldl max 0 products))

palindrome.hs

import Control.Applicative

main =
    -- http://en.wikibooks.org/wiki/Haskell/Applicative_Functors
    let products = liftA2 (*) (reverse [100..999]) (reverse [100..999])
        isPalindrome n = show n == reverse (show n)
        maxPalindrome = foldl max 0 (filter isPalindrome products)
    in putStrLn (show maxPalindrome)

sum.hs

main =
    let x = filter (\a -> a `mod` 3 == 0 || a `mod` 5 == 0) [1..999]
    in putStrLn (show (sum x))

sum_of_sqares.hs

main = putStrLn (show (sum [1..100] ^2 - (sum $ map (^2) [1..100])))

utils.sh

#!/bin/bash

profile_haskell() {
    ghc -prof -fprof-auto -rtsopts $1
    echo "Running..."
    ${1%%.hs}.exe +RTS -p
    cat ${1%%.hs}.prof
}