Haskellでミニマムな正規表現のmatch関数を実装してみる

「ビューティフルコード」（オーライリー・ジャパン）のしょっぱなの章で、 カーニハン先生がロブ・パイクさんのミニマムな正規表現のmatch関数のソースコードを紹介していた。

たった３０行ほどのC言語コードで、下記正規表現をサポートする。

文字	意味
c	文字cそのもの
.	任意の一文字
^	文字列の先頭にマッチ
$	文字列の末尾にマッチ
*	直前の文字の0回以上の反復

95％の用途はこれで足りると書いてあったが、さもありなん。 短くて日常のほとんどのケースで用が足せる簡潔なプログラムは、まさにUNIX精神そのもの。

この本のパイクさんのコードに触発されて、Haskellで同等のものを書いてみた。

ミニマム正規表現match関数Haskell版

match_here :: [Char] -> [Char] -> Bool
match_here [] _ = True
match_here (x:xs) []
    | x == '$' && xs == [] = True
    | otherwise = False
match_here (x:xs) (y:ys)
    | x == y || x == '.' = if xs /= [] && head xs == '*' 
                           then match_repeat x (tail xs) ys
                           else match_here xs ys
    | otherwise = False


match_repeat :: Char -> [Char] -> [Char] -> Bool
match_repeat _ [] _ = True
match_repeat _ _ [] = False 
match_repeat c (x:xs) (y:ys)
    | x == y = match_here xs ys
    | c == y || c == '.' = match_repeat c (x:xs) ys
    | otherwise = match_here xs (y:ys)


-- match regex string 
match :: [Char] -> [Char] -> Bool
match _ [] = False
match (x:xs) (y:ys)
    | x == '^' = match_here xs (y:ys)
    | match_here (x:xs) (y:ys) = True
    | otherwise = match (x:xs) ys

使用例

*Main> match "^a.*1" "abccfb1"
True
*Main> match "abc" "abccfb1"
True
*Main> match "c.*1$" "abccfb1"
True
*Main> match "ccd" "abccfb1"
False

ロブ・パイクさんのコードは、再帰とポインタを巧みに使っていて、 ほとんどC言語で関数型プログラミングをしているようなもの。

このプログラム構成のアイディアはそのまま使った感じだが、 コードを見ながら移植だとつまらないので、 一度みた構成を思い出しながら、Haskellで実装するというスタイルをとった。

Haskell初心者なので、実はもっと簡潔に書けるかもしれない。 が、実際書いてみるとHaskell言語はかなり見通しがよいと思った。 パターンマッチング、条件分岐や関数宣言の簡潔な記法、が効いているな。