Journal InTime

_ readFile/interact

コメントを参考に研究した結果、

readLines :: FilePath -> IO [String]
readLines path = do h <- openFile path ReadMode
                    cs <- hGetContents h
                    return $ lines cs

main = do paths <- getArgs
          liness <- sequence (map readLines paths)

は、readLinesのような定義をせずに

main = do paths <- getArgs
          lines <- concatMap lines `fmap` mapM readFile paths

と書けることがわかった。

readFileはRubyのFile.readのようなもので、pathを与えるとファイルのすべての 内容を文字列で返す(正確にはそういうアクションを返す。lazyなので読みこみは逐次必要になった時に起こる。)。

concatMapMみたいなのはないかなと思ったがrejectされていた。

また、interactという関数にString -> Stringという型の関数を与えると、標準入力を加工して標準出力に出力するような処理が簡単に書けるらしい。UNIXぽい。

_ 退院

とりあえず、やっと1か月の入院生活が終わって退院することができた。

でもまだ左腕の熱傷はあまり治っておらず、当面は週2回程度の通院で様子を見ることに。

主治医の先生の話だと、今の状態で植皮してもうまく行くとは限らないらしく、時間をかけて治す方針になった。 きれいに治るといいんだけど…。

_ 素数の計算

Haskellで素数を求めるコードは、以下のように簡潔に書ける。

sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x /= 0]
primes = sieve [2..]

main = print $ primes !! 1000

これが遅いのは有名だけど、実はSICPにも同じような例がある。

(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))

(define (divisible? x y) (= (remainder x y) 0))

(define (sieve stream)
  (cons-stream
   (stream-car stream)
   (sieve (stream-filter
           (lambda (x)
             (not (divisible? x (stream-car stream))))
           (stream-cdr stream)))))

(define primes (sieve (integers-starting-from 2)))

(display (stream-ref primes 1000))

MIT Schemeだとこのまま動いたが、Gaucheだと(use util.stream)した上でcons-streamはstream-consにする必要があるようだ。

比べてみるとHaskellの方が断然速い。

$ time ./prime
7927
./prime  0.11s user 0.00s system 95% cpu 0.122 total
$ time mit-scheme --batch-mode < prime.scm
7927mit-scheme --batch-mode < prime.scm  2.39s user 0.18s system 98% cpu 2.602 total
$ time gosh prime2.scm
7927gosh prime2.scm  14.84s user 0.06s system 99% cpu 14.979 total

別にSchemeが遅いと言いたいわけではなくて、このアルゴリズムは効率悪いけど、Haskell自体はやっぱり速いんだな、と。

しかし、Project EulerとかやるとやっぱりHaskellでも遅いのでprimesパッケージを使うのであった(ずるい)。 primesパッケージのprimesとかprimeFactorsはすごく速いけど、コード読んでもさっぱりわからないのでだれか解説してください。

_ Arrayで動的計画法

Haskellではデータがimmutableなので動的計画法はどうやるんだろうと思ったが、Arrayですっきり書けるようだ。

試しにグリッド上の経路の数を計算してみる。

import Data.Array

routeCount :: Int -> Int -> Integer
routeCount width height =
  routes ! (width, height)
    where routes = array ((0, 0), (width, height)) $
            -- 一番下の行の経路数はすべて1
            [ ((x, 0), 1) | x <- [0..width] ] ++
            -- 一番左の列の経路数はすべて1
            [ ((0, y), 1) | y <- [1..height] ] ++
            -- 残りは、左と下の点までの経路数の和
            [ ((x, y), routes ! (x - 1, y) + routes ! (x, y - 1))
              | x <- [1..width], y <- [1..height] ]

main = print $ routeCount 5 4

遅延評価のおかげで、routesの定義中でroutesを再帰的に参照できる。かっこいい。