Colorless Sight Wiki / ProjectEular/Common

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

最新の20件