krの日記： Haskellで速いwcを書いてみよう(6)

前のエントリの続きです。

ここからが本番で、気持も新たにHaskell版のwcを作り始めます。 まず、せっかくHaskellの標準モジュールにwordsとかlinesとかあるので、 できればこれらを使いたいところではありますが、すでに見た通り、 同じ入力をwordsとlinesに順に与えるやり方では、メモリがいくらあっても足りません。 入力を読みながら、行数・単語数・文字数を同時に数えていく必要がありそうです。

とっさに良い方法は思いつかないので、ここはwordsやlinesの使用をすっぱり諦め、 自前で行数や単語数を数えることにします。 これはtanakh氏の改良版や、C・C++版でも同様でした。

深いことは考えず、関数型言語でよくやる末尾再帰のパターンで第1版を書いてみましょう。

-- prog6
import Data.Char

wc:: String -> ( Int, Int, Int )
wc = wc' 1 0 0 0
    where
      wc':: Int -> Int -> Int -> Int -> String -> (Int, Int, Int)
      wc' s nl nw nc [] = (nl, nw, nc)
      wc' s nl nw nc ('\n' : cs) = wc' 1 (nl + 1) nw (nc + 1) cs
      wc' s nl nw nc  (c : cs)
          | isSpace c = wc' 1 nl nw (nc + 1) cs
          | otherwise = wc' 0 nl (nw + s) (nc + 1) cs

main = do
  cs <- getContents
  let (nl, nw, nc) = wc cs
  putStrLn $ (show nl) ++ " " ++ (show nw) ++ " " ++ (show nc)

このプログラムをprog6とします。アルゴリズムは、tanakh氏のC・C++版にほぼ倣いました。 ベタに再帰を書くのはイマイチHaskellらしくない気もしますが、OCamlやSchemeなどの関数型言語に慣れた人ならば、Haskellを知らなくても却って素直に読めるコードになっているんじゃないでしょうか。

さて、コンパイルして実行してみると……

% ./prog6 < /usr/share/doc/en/books/handbook/book.txt
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize' to increase it.

ということで、実は大きなファイルを喰わすと動きません。

さて何故でしょう、ということで、ここに正格評価型には無いちょっとした罠があったりします。

その続きは次のエントリで。