yunomuのブログ

酒とゲームと上から目線

Parsecを使って正規表現の代わりにパーサを与えるgrepのようなものを作る

Haskellやるならパーサ作っておかなきゃいけないかなって。

ということで試しにIPv4アドレスのパーサと、正規表現の代わりにパーサを与えるgrepのようなものを作ってみようかなと。
完成イメージはこんな感じ。(実際にはこの記事のコードの完成直前に固まりました)

main :: IO ()
main = do
    ls <- grep stdin ipv4addr
    mapM_ putStrLn ls

grep :: Handle -> Parser String -> IO [String]
ipv4addr :: Parser String

stdinのところはなんか適当なハンドルが入る感じ。

以降、やった順というか、悩んだ順にいきます。

IPv4アドレスパーサ

まずは順番に、自然数を読むパーサから。自然数は0からとします。いやnatって名前しか浮かばなかっただけですけど。

nat :: Parser Int
nat = read <$> many1 digit

Parsecが用意してくれてる数字パーサdigitと、パーサを1回以上連続適用するCombinatorのmany1を組み合わせて、"Parser [Char]"を返すパーサを作って(many1 digit)、readで[Char](=String)を数値Intに変換する。

IPv4アドレスはご存知のように"127.0.0.1"みたいな、ピリオド区切りで0-255の整数が4つつながってる。
ParsecにはsepByっていう、パーサと区切り文字用のパーサを与えて、区切り文字を捨てつつ配列を返してくれるパーサコンビネータがある。ので、これを使ってもいいんですけど、区切りは4つって決まってるわけだし、「5つあるぞコノヤロウ!」って文句を言うよりは後の事は他の人に任せて「4つきた時点で読むのをやめる」って方がいいかなぁ。
ということでこんなふうにした。

-- n.n.n.n # (0 <= n <= 255)
ipv4addr :: Parser [Int]
ipv4addr = sepByN 4 byte (char '.')
  where
    byte :: Parser Int
    byte = do n <- nat
              when (n > 255) $ unexpected "IPv4 should be 0-255"
              return n

-- p (sep p){n-1}
sepByN :: Int -> Parser a -> Parser b -> Parser [a]
sepByN n p sep
    | n <= 0    = return []
    | otherwise = (:) <$> p <*> count (n-1) (sep *> p)

n回のsepByを作った(sepByN)。"count n p"という、pをn回繰り返すコンビネータがあったので、それを使って。0以下を指定する奴は死ねっていいたいところだけど、countの仕様に習って空リストで許すことにした。
"*>"は左を捨てて右を使うみたいな、Applicativeの関数です。逆の"<*"もあるし、両方使うのがつまり"<*>"ってことみたいです。右と左のどっちかわからなくなって毎回調べてます。
あと、byteはnatで取ってきた数値が255より大きくなってないかを調べるだけの関数。natは負の数を返さないのでこれでよい。こういう「型に載らない仮定」にバグが入り込む気がしないでもないけど。まあいいや。
この辺を組み合わせて、IPv4アドレス文字列をパースして数値のリストにするipv4addrができる。

だけど、よく考えると私はgrep的なものが作りたいわけだから、IPv4アドレスを数値リストでもらっても嬉しくない。型はParser Stringだろう。最初にそう書いたし。(この時点では書いてなかった)
ということで、数値リストを"."で区切った文字列に変換する関数(addr2str)を作って、<$>で変換してみる。

ipv4str :: Parser String
ipv4str = addr2str <$> ipv4addr

addr2str :: [Int] -> String
addr2str (n:ns) = show n ++ show' ns
  where
    show' []     = []
    show' (a:as) = "." ++ show a ++ show' as

何か本末転倒な気がする。

というか、これじゃgrep的に出た結果が、入力した文字列そのものじゃなくて、入力した文字列の一部を変換したものになってしまう。見た目は同じかもしれないけどね。
ということで、StringはStringのまま扱うことにする。そうすると値のチェックの場所が変わるし、sepByNのセパレータも捨てちゃいけなくなるし、natとか作ったのは無駄だったことになる。いやあれくらいいつでも作れよという気もする。

-- n.n.n.n # (0 <= n <= 255)
ipv4addr :: Parser String
ipv4addr = sepByNS 4 byte (char '.')
  where
    byte :: Parser String
    byte = do
        n <- many1 digit
        when ((read n) > 255) $ unexpected "IPv4 should be 0-255"
        return n

    -- p (sep p){n-1}
    sepByNS :: Int -> Parser String -> Parser Char -> Parser String
    sepByNS n p sep
        | n <= 0    = return []
        | otherwise = foldl (++) "" <$> sepByNS'
      where
        sepByNS' = (:) <$> p <*> count (n-1) sepp
        sepp = (:) <$> sep <*> p

sepByNは、ああもうこれどうせStringしか使えないからStringを返すパーサにしちゃえばいいじゃないとか思ってるうちにいつの間にかsepBYNSって名前が変わって内部関数になった。
というわけでこれでめでたくipv4addrはStringのパーサになりました。同時にbyteもStringのパーサになり、値の範囲のチェックはこの中で一旦数値に変換してやってます。
まあこんなものでしょうか。

grepのようなもの

続いてgrepのようなものを作る。
まず、パーサを使って、マッチしたら一行まるごと取り出す関数を作る。なんかこれができたらいきなり終わる気がする。

matchLine :: Parser String -> Parser String
matchLine p = try matchLine' <|> ((:) <$> anyChar <*> (matchLine p))
  where
    matchLine' = (++) <$> p <*> many anyChar

このパーサに渡される文字列には改行などが含まれないものとする。こういう「型に載らない仮定」にバグが入り込む気がしないでもないけど。まあいいや。
今回は関数名を変えればいいだけのような気がしますね。
matchLine'はパーサpにマッチしたらそこから最後までの文字列を返す。
matchLineはmatchLine'で読めなかったら一文字読んで覚えておいてもう一度matchLineを試す。というのを繰り返して、matchLine'で読める部分(=pで読める部分)が無かったら残念でしたという感じ? 効率悪そうだな。

これを使って、いよいよgrepを作る。いまさらだけどgrepのreってregular expressionのreじゃなかったっけ。gとpは知らん。

grep :: Handle -> Parser String -> IO [String]
grep h p = grep' []
  where
    grep' :: [String] -> IO [String]
    grep' ss = catch (grep'' ss) (eofError ss)

    grep'' ss = do
        l <- hGetLine h
        lss <- case parse (matchLine p) "" l of
          Left err -> return ss
          Right s  -> return (ss ++ [s])
        grep' lss

    eofError :: a -> IOError -> IO a
    eofError a e = if isEOFError e then return a else ioError e

grep'では、EOFErrorを検出して握りつぶしつつ蓄積した文字列リストを返す。
grep''では、1行読み込んで、パーサでマッチしたら蓄積した文字列リストに加える。ダメだったら次に進む。

こんなんでいいんじゃないかな。
そして最初に出たmain関数と合体して実行してみる。

% ifconfig | ./grep-ipv4
        inet 127.0.0.1 netmask 0xff000000

するとこのように、無線LANが切れてIPアドレスがなくなっていることに気づく。

うまくいったっぽいですね。

できあがったのがこちらです。
exercises/grep-ipv4 at master · yunomu/exercises · GitHub