----------------------------------------
--    Sorting
----------------------------------------
-- Quick SOrt
--
quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs
----------------------------------------
--    Primes, Factors and Multiples
----------------------------------------
-- Given a list of candiatates and a target number return the first candiate
-- which is a factor of the number  
firstFactor :: (Integral a, Num a) => [a] -> a -> a
firstFactor factors number  = head [ x | x <- factors, number `mod ` x == 0 ]

primeFactor :: Integer -> Integer
primeFactor x = firstFactor tenThousandPrimes x

primeFactors :: [Integer] -> Integer -> [Integer]
primeFactors factors n 
    | factor == n = quicksort (factors ++ [n])
    | otherwise   = primeFactors (factors ++ [factor]) (quot n factor)
    where factor = primeFactor n
-- ** removeFactorFromList **
--
-- Remove numbers which are a multiple of the first arg from the list
--
--     (a)   : The factor
--     ([a]) : The list to trim
--
removeFactorFromList :: (Integral a) => a -> [a] -> [a]
removeFactorFromList fact xs = [x | x <- xs, x `mod` fact /= 0]

-- ** findPrimes **
--
-- Acts like the sieve of Eratosthenes:
--   1. Assume the head element is prime
--   2. Remove all multiples of the prime from the rest of the list
--   3. continue...
--
-- Params: 
--  1 [a]: A list of know primes
--  2 [a]: A list of numbers to sieve
-- Returns [a]: A list of primes
findPrimes :: (Integral a) => [a] -> [a] -> [a]
findPrimes primes [] = primes
findPrimes primes (prime:[]) = primes ++ [prime]
findPrimes [] (prime:others) = findPrimes [prime] (removeFactorFromList prime others)
findPrimes primes (prime:others) = findPrimes (primes ++ [prime]) (removeFactorFromList prime others)


-- ** primes **
--
-- Returns primes below N
--
-- Params:
--  1 a: The max value allowed for the prime
-- Returns [a]: A list of primes
primes :: (Integral a) => a -> [a]
primes x = findPrimes [] [2..x]

tenThousandPrimes = primes 10000 

main = print tenThousandPrimes
