Project Euler solutions in Haskell

peuler.hs

import Control.Applicative

--
-- Utils
--

-- Ordered List: difference
minus :: (Ord a) => [a] -> [a] -> [a]
minus (x:xs) (y:ys) = case (compare x y) of
    LT -> x : minus  xs  (y:ys)
    EQ ->     minus  xs     ys
    GT ->     minus (x:xs)  ys
minus xs _ = xs

-- Ordered List: union
union :: (Ord a) => [a] -> [a] -> [a]
union (x:xs) (y:ys) = case (compare x y) of
    LT -> x : union  xs  (y:ys)
    EQ -> x : union  xs     ys
    GT -> y : union (x:xs)  ys
union xs [] = xs
union [] ys = ys


-- Fibonacci series
fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

-- Primes: Eratosthenes Sieve
-- http://www.haskell.org/haskellwiki/Prime_numbers
primesTo :: Integral a => a -> [a]
primesTo n = 2 : sieve [3,5..n] where
    sieve []     = []
    sieve (p:xs) = p : sieve (xs `minus` [p*p, p*p+2*p.. n])

-- Primes: Factorization
primeFactors :: Integral a => a -> [a]
primeFactors n = fact n 2 where
    fact n start
        | n == start         = [n]
        | n `mod` start == 0 = start : (fact (n `div` start) start)
        | start == 2         = fact n 3
        | otherwise          = fact n (start + 2)

-- Reverse an integer
-- eg: 123 -> 321, 530 -> 35
integralReverse :: Integral a => a -> a
integralReverse n = foldl f 0 (rests n) where
    rests n = takeWhile (>0) $ iterate (`div` 10) n
    f acc x = acc * 10 + (x `mod` 10)

-- Palindromes: integer check
integralIsPalindrome :: Integral a => a -> Bool
integralIsPalindrome n = n == integralReverse n


-- Problem solutions
--
-- Instructions for each problem at http://projecteuler.net/problem=N
--

p1 = sum [x | x <- [1..999], x `mod` 3 == 0 || x `mod` 5 == 0]
-- 233168

p2 = sum [x | x <- takeWhile (<= 4000000) fibs, even x]
-- 4613732

p3 = last $ primeFactors 600851475143
-- 6857

p4 = maximum $ filter integralIsPalindrome $ (*) <$> [100..999] <*> [100..999]
-- 906609


main = do
    putStrLn $ "Problem 1: " ++ show p1
    putStrLn $ "Problem 2: " ++ show p2
    putStrLn $ "Problem 3: " ++ show p3
    putStrLn $ "Problem 4: " ++ show p4