- 追加された行はこの色です。
- 削除された行はこの色です。
[[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
-- http://www.sampou.org/cgi-bin/haskell.cgi?Programming%3a%b6%cc%bc%ea%c8%a2%3a%c1%c8%b9%e7%a4%bb#H-cnnhzd
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