ProjectEular

2010-08-01 (日) 19:44:40 版

```-- Common.hs

module Common (
fibs
,   factorize
,   divisors
,   proper_divisors
,   is_prime
,   permutations
) where

------------------------------
-- Export functions
------------------------------

-- Get Fibonacci sequence
fibs :: (Integral a) => [a]
fibs = 1 : 2 : zipWith (+) fibs (tail fibs)

-- Prime factorization
factorize :: (Integral a) => a -> [a]
factorize n = factorize_iter n (2:[3,5..])

-- Get divisors
divisors :: (Integral a) => a -> [a]
divisors num = divisors_iter num [1..]

-- Get proper divisors (== divisors of N except for N)
proper_divisors :: (Integral a) => a -> [a]
proper_divisors = init . divisors

-- Is a prime number or not
is_prime :: (Integral a) => a -> Bool
is_prime n = is_prime_iter n (2:[3,5..])

-- Get all permutations
permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations xs = concat [ map (x:) (permutations xs') | (x,xs') <- f xs ]
where
f []     = []
f (x:xs) = (x,xs) : [ (x',x:xs') | (x',xs') <- f xs ]

------------------------------
-- Non-export functions
------------------------------

-- For prime factorization
factorize_iter :: (Integral a) => a -> [a] -> [a]
factorize_iter n (x:xs)
| n < x^2      = [n]
| mod n x == 0 = x : (factorize_iter (div n x) (x:xs))
| otherwise    = factorize_iter n xs
-- For getting divisors
divisors_iter :: (Integral a) => a -> [a] -> [a]
divisors_iter n (x:xs)
| n < x^2                = []
| mod_ == 0 && div_ == x = x : (divisors_iter n xs)
| mod_ == 0 && div_ /= x = x : (divisors_iter n xs) ++ [div_]
| otherwise              = divisors_iter n xs
where (div_,mod_) = divMod n x

-- For is_prime
is_prime_iter :: (Integral a) => a -> [a] -> Bool
is_prime_iter n (x:xs)
| n <= 1       = False
| n < x^2      = True
| mod n x == 0 = False
| otherwise    = is_prime_iter n xs```