2016-06-01

Project Euler #1, #2

Project EulerをHaskellで解いてみることにする(というか、元々Pythonで解いてて「これなら純関数型の方がやりやすくね？」と思ったのが発端)。

Problem #1は3または5の倍数を取り出す問題。これは特に問題なく書けた:

main :: IO ()
main = do
    print $ sum [ n | n <- [1..999], n `mod` 3 == 0 || n `mod` 5 == 0 ]

Problem #2はフィボナッチ数列の問題。Pythonでは既に解いていたので同じことをするだけだと思ったのだが、色々とつまづきポイントがあった。初学者だから仕方ないね。

最初に書いたのはこんなコード:

fib 1 = 1
fib 2 = 2
fib n = fib (n-1) + fib (n-2)

main :: IO ()
main = do
    print $ sum $ filter even $ takeWhile (< 4000000) $ map fib [1..]

実は無限リストの扱いがよくわからず、ここまででも若干手こずった。当初は 4000000 未満の要素を取り出す処理をリスト内包や filter で書いて無限ループになっており、色々調べた結果 takeWhile が正解だとわかった。リスト内包や filter はあくまでフィルタ条件を指定するだけで、条件を満たさなくなったら打ち切るとは言ってないんだな。

それでさっきのコードだが、答えは正しい。しかし実行速度がクッソ遅い:

$ time python3 fib_even.py
4613732
python3 fib_even.py  0.02s user 0.00s system 88% cpu 0.023 total

$ time runghc fib_even.hs
4613732
runghc fib_even.hs  12.82s user 0.08s system 100% cpu 12.889 total

コンパイルしてもまだPythonより遅い(-O2, -O3 は -O と変わらなかったので省略):

$ ghc -o fib_even fib_even.hs
$ time ./fib_even
4613732
./fib_even  1.34s user 0.01s system 99% cpu 1.358 total

$ ghc -O -o fib_even fib_even.hs
$ time ./fib_even
4613732
./fib_even  0.35s user 0.01s system 99% cpu 0.368 total

調べてみたらこの件は約6年前に話題になっていたらしい:

Haskellの「fib = 1:1:zipWith (+) fib (tail fib)」がとても遅い件のまとめ

この際だから全部読んで完全に理解…

するわけないだろ！いい加減にしろ！のっけからこういう闇が深そうな話には関わりたくないの！

つーわけでリンク先にあった末尾再帰版だけパクって試してみることにする:

fib 1 = 1
fib 2 = 2
fib n = fib' n 1 2

fib' 1 _ y = y
fib' n x y = fib' (n-1) y (x+y)

main :: IO ()
main = do
    print $ sum $ filter even $ takeWhile (< 4000000) $ map fib [1..]

これだと

$ time runghc fib_even.hs
4613732
runghc fib_even.hs  0.13s user 0.02s system 95% cpu 0.151 total

コンパイルなしでもPythonよりわずかに遅い程度で済むようだ。再帰で遅くなりすぎる場合は末尾再帰化を考えてみることにしよう。

というか今回は無限リストも絡んでたので、遅いだけなのか無限ループしてるのかわかりにくかったりして色々面倒だなーと思った（小並感）

2016-06-01

Haskell 事始め

Haskellをやってみようかと思う。関数型言語は昔 Emacs Lisp が全く理解できず投げ出したままなんだけど。

とりあえず最初にチラ見したもの(全部読んだとは言ってない):

当初リファレンスがどこにあるのかよくわからなかったが、多分GHC Documentationを見ればいいのだろう。Prelude ってのが組み込み関数モジュールみたいなもんだと思われる。

記号類はググラビリティが悪いので、Haskellの演算子について纏めてみたという記事もブックマークしておくことにする。

手始めに FizzBuzz を書いてみた(入力処理は省略):

fizzbuzz n
    | n `mod` 15 == 0 = "FizzBuzz"
    | n `mod`  3 == 0 = "Fizz"
    | n `mod`  5 == 0 = "Buzz"
    | otherwise       = show n

main :: IO ()
main = do
    print (map fizzbuzz [1..100])

print の部分は括弧を避けるために $ 演算子を使うこともできる模様:

print $ map fizzbuzz [1..100]

Lisp 臭を消すのに使えそう。合成関数を作る . 演算子も有用か。

ところでこの記事はhateblo.vimを使って Markdown で投稿したのだが、段落中の改行が空白に変換されてしまうのは仕様なんだろうか。改行を入れると以下の段落のようになる:

この段落は改行を入れまくってます

仕方ないので当面はブログを書くときだけ set textwidth=0 しようと思う。Vim は物理行単位での移動ができる(j, k を gj, gk にリマップ)のでまぁこれでも困らないのだが。他の人はどうしてるんだろうな?