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
