(200) Days of Haskell - Ruby 厨だけどハスケルやるよ

(7) 素因数分解

function | 17:20

module Main where
    import System
    isPrime :: Int -> Bool
    isPrime n | n <= 1    = False
              | n == 2    = True
              | otherwise = all (/= 0) $ map (mod n) $ enumFromTo 2 $ toUpperSqrt n
                          where
                              toUpperSqrt = ceiling . sqrt . fromIntegral

    enumPrimes :: Int -> [Int]
    enumPrimes n = filter isPrime $ (enumFromTo 1 n)

    minPrime :: Int -> Int
    minPrime n = (filter (\x -> n `mod` x == 0) $ enumPrimes(n)) !! 0

    factor :: Int -> [Int]
    factor 1 = []
    factor n = [minPrime(n)] ++ (factor $ n `div` minPrime(n))

    main = do
        n <- getArgs
        (putAll $ factor $ read $ n !! 0) >> putStrLn ""
            where
                putAll = mapM_ (putStrSpace . show)
                putStrSpace str = putStr $ str ++ " "

isPrime の自作にすごい苦労した……。

以下はコンパイルが通るが、動かない。

module Main where
    isPrime n | n <= 1    = False
              | n == 2    = True
              | otherwise = all (/= 0) $ map (mod n) $ enumFromTo 2 $ toUpperSqrt n
                          where
                              toUpperSqrt = ceiling . sqrt

Prelude> :load "isprime.hs"
[1 of 1] Compiling Main             ( isprime.hs, interpreted )
Ok, modules loaded: Main.
*Main> isPrime 1234567

<interactive>:1:1:
    Ambiguous type variable `a0' in the constraints:
      (RealFrac a0) arising from a use of `isPrime'
                    at <interactive>:1:1-7
      (Num a0) arising from the literal `1234567' at <interactive>:1:9-15
      (Integral a0) arising from a use of `isPrime'
                    at <interactive>:1:1-7
      (Floating a0) arising from a use of `isPrime'
                    at <interactive>:1:1-7
    Probable fix: add a type signature that fixes these type variable(s)
    In the expression: isPrime 1234567
    In an equation for `it': it = isPrime 1234567

これは、 mod と sqrt とで取るべき型が違うためだ。

*Main> :t mod
mod :: Integral a => a -> a -> a
*Main> :t sqrt
sqrt :: Floating a => a -> a

明示的に Floating に変換すればOK。 http://www.sampou.org/haskell/tutorial-j/numbers.html も参照せよ。

module Main where
    isPrime n | n <= 1    = False
              | n == 2    = True
              | otherwise = all (/= 0) $ map (mod n) $ enumFromTo 2 $ toUpperSqrt n
                          where
                              toUpperSqrt = ceiling . sqrt . fromIntegral

こうであれば、どっちも Integral を受け入れる。

$ ./factor 11223344
2 2 2 2 11 43 1483 

大丈夫です、 Haskell モヒカン族の皆さんにコメントされるまでもなく、

リスト内包表現、 1 : [2, 3, 4] のようなリストをくっつける表現などが身についてないことが分かりますね、、、

• http://d.hatena.ne.jp/mokehehe/20070615/factorization

10 倍綺麗な書き方。

ツイートする