[[ProjectEular]]

2010-07-23 (金) 23:06:43 版
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
トップ   差分 バックアップ リロード   一覧 単語検索 最終更新   ヘルプ   最終更新のRSS