前回は、スペル修正プログラムに必要なword関数(外部のテキストファイルを読み込んで単語列を作り出す)とtrain関数(その単語列から単語->出現回数なるマップを作り出す)を定義した。ここから一気に後半の部分を完成させたいところだけど、すこしコードを綺麗にしてその2の準備をしたい。やりたい準備は

文字列処理を大規模テキストには効率の悪いString型から効率のよいText型に変える
URLをフェッチする部分を別のモジュールにしてローカルのtmpフォルダにキャッシュする機能を付け加える

というところ。

Haskellにおける文字列の種類

参考文献

Haskell Tips (文字列編) - りんごがでている

本物のプログラマはHaskellを使う - 第2回多相性（ポリモーフィズム）への理解を深める：ITpro

（6/6）本物のプログラマはHaskellを使う - 第45回 GHCの性能測定機能でボトルネックを探す：ITpro

参考先で解説されているとおり、Haskellには主に３つのテキストの取り扱い方があって

String
ByteString
Text

の3通りがあるようだ。

Stringは単なるCharのリストでサイズ・速度共にあまり優れていないようだ。なので、大きなテキストの処理とかには向いていなそう。マルチバイト処理などはうまく出来るようになっているとのこと。なので大きなテキストを扱う予定のないカジュアルな用途向けのようだ。

ByteStringは1文字が1ワード、1バイトの文字列で、マルチバイト処理なんかはできないけど、効率よく文字列処理ができるらしい。どうもそうすると文字列というよりはバイト列という感じがする。あとは必ず8バイトになるアルファベットだけの文章の時とかは良さそうだ。

Text はマルチバイト処理もある効率のよいテキスト処理向けのようだ。なので今回はStringをやめてこれを使うように改造していこう。

wordsFromTextの正規表現をやめてTextライブラリを全面的に使っていく

まず、正規表現を使っている部分をやめることにする。再帰と正規表現というのはいかにも遅そうなのとTextモジュールにはsplitという便利そうな関数があるのでこれに切り替えるのもついでにやってしまおう。

wordsFromText :: String -> [String]
wordsFromText textStr = scan (makeRegex "([a-z]+)") $ map toLower textStr

これが肝心の単語列を生み出す部分の変更前。これがおそらく大きなテキストを受け取って単語列を返すText -> [Text]になるはず。

まずはTextが使えるようにTextパッケージをインストールしてcabalファイルにTextを追加しよう。

build-depends:   base,HTTP,regex-posix,regex-compat,containers,text

これで、Textパッケージが使えるようになったのでTextモジュールをインポートしてみる。

import qualified Data.Text as Text
import Data.Text ()

これでText型をText.Textで使えるようになった。つまりゴールの関数型はText.Text -> [Text.Text]となるはず。TextモジュールのsplitとtoLowerを使いながら以下のようにしてみた。

wordsFromText :: Text.Text -> [Text.Text]
wordsFromText textStr = Text.split (`elem` " ,\"\'\r\n!@#$%^&*-_=+()") (Text.toLower textStr)

正規表現を使って分割をしていた部分を空白や思いつく限りの記号で分割するようにして、さらにText.toLowerで小文字に変換している。ワンライナーになった。これでscan関数をもろとも消し去ることができる。さらに誰かがTextモジュールに高速化とか改善を加えたら素直にそのメリットに与れる。

train関数を末尾再帰に

続いて全体をTextを使うように変えていく。次のターゲットはtrain関数だ。

ところで、おそらく前回のプログラムでPeter Norvig先生のページに有るbig.txtを処理すると途中で止まってしまうはず。理由はstack overflow。train関数は末尾再帰でない再帰関数なので、単語列を処理していくうちにスタックが深くなっていって止まってしまうのだ。なので、Textを使うように変えつつ、ついでにこれを末尾再帰の関数に書き換える。

末尾再帰というと頭に浮かんだのはfoldl関数。左折り畳み関数は言語の東西を問わず末尾再帰なはず。なのでnaiveに左折り畳み関数を使ってMap.insertWithKeyを呼ぶように以下のとおり書き換えてみた。さらにwordsFromTextが[Text.Text]を返すようになったのでそれも合わせて変えてみた。まずはData.Mapのインポートの仕方を

import Data.Map (insertWithKey, empty)

こうだったのをimport qualifiedを使って

import qualified Data.Map as Map

こう変えてみる。こうするといままでinsertWithKeyと書いていたものはMap.insertWithKeyと書かないといけなくなる。利点としては名前空間がわかりやすくなるのでデータ型を間違えなくていいとかそんな感じだろうか。

    countWords [] = Data.Map.empty
    countWords (x:xs) =
      let s = countWords xs in
          Data.Map.insertWithKey (\k x y ->x + y)  x 1 s
    train features = countWords features

こうだったのを

    train :: [Text.Text] -> Map.Map Text.Text Int
    train list =
        List.foldl' (\map element -> Map.insertWithKey (\_ v y -> v + y) element 1 map) Map.empty list

こう書き換えてみた。再帰からfoldlになった。再帰は基本的に強力な手法で、なんでも出来てしまうので、なんでも出来てしまうがゆえに何をしているのかぱっと掴みづらい。foldlはそれよりも力が弱い（できることが限られている）2つの方法がある場合はできることが限られている弱い方法を取ることを考えてみるとあとあと楽になれる。foldlよりもさらに、例えばmapとかfilterとかはさらにできることが限られているぶん何をやっているかが明瞭になる。

さて、再帰をやめてさらにスリムになった。List.foldl'はfoldlの正格評価バージョンで遅延評価を行わない。スタックオーバーフローを回避するには遅延評価を避けるのが一番だと思ったので、この'が付いているバージョンを選んでみた。'を付けないバージョンは試していないのでわからない。興味がある人は'なしバージョンでもスタックオーバーフローしないかどうか試してみると面白いかも。

foldl'の読み方としては

まずMap.emptyから始める
listの最初の要素をひとつとってMap.emptyとlistの最初の要素elementを第1引数の関数に放り込む
その結果のMapを覚えておいて
listの次の要素をひとつとってそのMapとlistの2番めの要素elementを第1引数の関数に放り込み...

という感じ。

fetchUrlの型を合わせる

ここで一度ビルドできるようにしたいのでfetchUrlの型を合わせたい。fetchUrlかいまStringを返すのでこれをText.Textを返すように変えてみよう。といっても最後に返すときにText.packしてStringをText.Textに変えるだけだ。

    fetchUrl :: String -> IO Text.Text
    fetchUrl url = do
        eitherResponse <- (simpleHTTP . getRequest) url
        case eitherResponse of
            Left _ -> do
                hPutStrLn stderr $ "Error connecting to " ++ show url
                return $ Text.pack ""
            Right response ->
                return $ Text.pack (rspBody response)

これで全体的にファイル読み込み部分をTextを使うように書き換えることができた。

まとめ

今回のコード変更まとめてみると以下のようになった。

module Main where
    import Text.Printf (printf)
    import Network.HTTP
    import System.IO
    import qualified Data.Text as Text
    import Data.Text ()
    import qualified Data.List as List
    import qualified Data.Map as Map

    main = do
        let url = "http://textfiles.com/humor/computer.txt"
        printf "Downloading %s...\n" url
        respStr <- fetchUrl url
        printf "Completed.\n"
        print $ train $ wordsFromText respStr

    wordsFromText :: Text.Text -> [Text.Text]
    wordsFromText textStr = Text.split (`elem` " ,\"\'\r\n!@#$%^&*-_=+()") (Text.toLower textStr)

    train :: [Text.Text] -> Map.Map Text.Text Int
    train =
        List.foldl' (\map element -> Map.insertWithKey (\_ v y -> v + y) element 1 map) Map.empty

    fetchUrl :: String -> IO Text.Text
    fetchUrl url = do
        eitherResponse <- (simpleHTTP . getRequest) url
        case eitherResponse of
            Left _ -> do
                hPutStrLn stderr $ "Error connecting to " ++ show url
                return $ Text.pack ""
            Right response ->
                return $ Text.pack (rspBody response)

cabalファイルは次のようになった。

name:              spllerD
version:           1.0
Build-Type:        Simple
cabal-version:     >= 1.2

executable spllerD
  main-is:         Main.hs
  hs-source-dirs:  src
  build-depends:   base,HTTP,containers,text
  ghc-options:     -Wall -O2

正規表現ライブラリとか使わなくなったものは全部バッサリ消してみた。あとghc-optionsで-Wallと-O2をたしてみた。

-Wallはコンパイル時警告をすべて出すように指示するオプション。これをつけるとコンパイルエラーではないけど無駄なコードとか良くないコードに警告を出してくれる(例えば正規表現ライブラリはもういらないよ、とか)。 -O2はコンパイル最適化の程度を指示するオプション。詳しくはPerformance/GHC - HaskellWikiとかがわかりやすいかも。

今回は全体的にTextを使うように書き換えてみた。少し気になったのだが、デバッグするときに走らせるたびにURLをフェッチするからすごい遅い、し、なんかダウンロード元のサーバにアタックしてるみたいに思われても嫌かも。なので、最初に書いたとおり、もう少しだけ回り道をしてURLをフェッチするけどローカルにもキャッシュするナイスなやつを次回は作ってみよう。

euphonictechnologies’s diary

Haskell超初心者の日記です。OCamlが好きです。

Haskellでものすごく簡単なスペル修正プログラムを作ってみる - その1.5:文字列処理をTextモジュールを使うようにする

Haskellにおける文字列の種類

wordsFromTextの正規表現をやめてTextライブラリを全面的に使っていく

train関数を末尾再帰に

fetchUrlの型を合わせる

まとめ