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