Hatena::Grouphaskell

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

2011-10-13

(7) 素因数分解

| 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

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

*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] のようなリストをくっつける表現などが身についてないことが分かりますね、、、

10 倍綺麗な書き方。

pi8027pi80272011/10/14 17:15(!!) は失敗するケースがあるので、より正しさが自明である書き方をしたい。と考えると、

factorization :: Int -> [Int]
factorization = factorization' 2

factorization' :: Int -> Int -> [Int]
factorization' _ 1 = []
factorization' n m
| m `mod` n == 0 = n : factorization' n (m `div` n)
| otherwise = factorization' (succ n) m

udzuraudzura2011/10/14 17:20なるほど、すごく綺麗ですね……。

udzuraudzura2011/10/14 17:20僕の書いた感じだとまだまだ手続き型っぽいオーラが出てます…

2011-10-11

(6) sort と sortBy

| 10:55

import List で使えます。

module Main where
    import List
    p = print . show
    firstDigitOrder a b | (mod a 10) < (mod b 10) = LT
                        | otherwise               = GT
    main = do
        p $ sort [45, 12, 34, 58, 27, 16]
        p $ sortBy firstDigitOrder [45, 12, 34, 58, 27, 16]

sortBy は、ルッビ~的なイメージで変換用関数を渡すのではなく、ソート対象の二値を取って Ordering を返す関数を渡す。

ルッビ~風 sortBy は、適当に toOrdering のような関数を定義すればできそう、というか、

module Main where
    import List
    p = print . show
    toOrdering fn a b | (fn a) < (fn b) = LT
                      | otherwise       = GT
    main = do
        p $ sort [45, 12, 34, 58, 27, 16]
        p $ sortBy (toOrdering (\x -> mod x 10)) [45, 12, 34, 58, 27, 16]

pi8027pi80272011/10/11 14:10toOrdering (\x -> mod x 10) は compare `on` flip mod 10 と書けます。
import Data.Function

udzuraudzura2011/10/11 15:19かっこいいですね!
http://www.haskell.org/ghc/docs/6.12.1/html/libraries/base/Data-Function.html#v%3Aon
この辺と見受けられるので次回見てみます

2011-10-06

(5) FizzBuzz

| 18:24

四日坊主だと思った? でも残念、

module FB where
    fizzBuzz n = case (n `mod` 3, n `mod` 5) of
                      (0, 0)    -> "FizzBuzz"
                      (0, _)    -> "Fizz"
                      (_, 0)    -> "Buzz"
                      otherwize -> show n
module Main where
    import System
    import FB
    main = do
        a <- getArgs
        mapM_ print $ map fizzBuzz [1 .. (read $ a !! 0)]

この発表 の F# のサンプルが格好良かったので真似した。まあ、敢えて間違った場合らしいですが……

Haskell でも警告が出ます。

module FB where
    fizzBuzz n = case (n `mod` 3, n `mod` 5) of
                      (0, _)    -> "Fizz"
                      (_, 0)    -> "Buzz"
                      (0, 0)    -> "FizzBuzz"
                      otherwize -> show n
FB.hs:2:18:
    Warning: Pattern match(es) are overlapped
             In a case alternative: (0, 0) -> ...

ファイルを二つに分けた際は、

ghc -o fb fb_main.hs FB.hs

こんな感じでいい、のか?

pi8027pi80272011/10/07 18:57main = readLn >>= mapM_ (print . fizzBuzz) . enumFromTo 1

udzuraudzura2011/10/08 09:28試してみます!!!

2011-09-29

(4) map と MapM / mapM_

| 20:11

Prelude> map print ["hoge", "piyo", "fuga"]

<interactive>:1:1:
    No instance for (Show (IO ()))
      arising from a use of `print'
    Possible fix: add an instance declaration for (Show (IO ()))
    In a stmt of an interactive GHCi command: print it
Prelude> mapM_ print ["hoge", "piyo", "fuga"]
"hoge"
"piyo"
"fuga"
Prelude> :t mapM putStrLn ["hoge", "piyo", "fuga"]
mapM putStrLn ["hoge", "piyo", "fuga"] :: IO [()]
Prelude> :t map putStrLn ["hoge", "piyo", "fuga"]
map putStrLn ["hoge", "piyo", "fuga"] :: [IO ()]

[IO ()] だと、 Showインスタンスでなくて、 IO [()] ならいいよということなのだろうがょくゎかりません…。何が違うのか。

tsurushuutsurushuu2011/09/29 21:49ghciの表示は、ただ単に、「Showのインスタンスを表示する」わけでは無かったはずですよ。

参考
http://www.kotha.net/ghcguide_ja/7.0.4/interactive-evaluation.html

とくに、IO [()]は、そのものがIO aなので、ghciが、気を利かせて、IO動作として実行してくれるのですが、

[IO ()]の場合は、IO ではなく、あくまでも、「リスト」なので、この状態では、IO動作としての実行をしないのだと思います。
(かつ、Showのインスタンスでもないので、表示も出来ない)

udzuraudzura2011/09/30 11:06なるほど、たしかにprintやpurStrLnでは返ってきた型のほうは表示していませんね、、、
説明読みましたが、雰囲気は分かっても理解できているか怪しいです><

2011-09-28

(3) ハノイの塔を解く

| 15:53

自分で色々頑張った結果、できなかった。「過程を出力する」のができない。

軽く調べた感じ、方針。

  • 移動する過程を、文字列でも [(Char, Char)] でもいいので生成していく
  • 生成したデータを最後に出力する
module Main where
  hanoi :: Int -> IO()
  hanoi x = putStrLn $ hanoiMove(x, 'a', 'c', 'b')
  hanoiMove :: (Int, Char, Char, Char) -> [Char]
  hanoiMove (1, from, to, via) = [from] ++ " -> " ++ [to] ++ "\n"
  hanoiMove (height, from, to, via) =
    hanoiMove(height - 1,from, via, to) ++ 
    hanoiMove(1, from, to, via) ++ 
    hanoiMove(height - 1, via, to, from)
  
  -- sample
  main = hanoi 4

Ruby 厨時代が長かったため、インデントが半角2つなんだけれど、何か違和感…… 幅いくつが標準的なんだろう?

$ ghc hanoi.hs
[1 of 1] Compiling Main             ( hanoi.hs, hanoi.o )
Linking hanoi ...
$ ./hanoi 
a -> b
a -> c
b -> c
a -> b
c -> a
c -> b
a -> b
a -> c
b -> c
b -> a
c -> a
b -> c
a -> b
a -> c
b -> c

は、はい。

* * *

を大変参考にした、というかデータ構造以外一緒。

mapM_ って何だろう? と思ったので調べた。

次回は上記記事を写経する。

参考になりそう

本物のプログラマ~を目指そう。

あと、7つの言語なにがしのHaskellの課題、その他の言語の課題をHaskellで解く、とかをしたい。形だけHaskellの本を買う(死亡フラグ)よりあるものでできる限り頑張ろうという方針。