Festaというイベントで、「regex-applicative」というパッケージの紹介を致しました。今回はその際使用したスライドを、ブログ記事として詳しく共有させていただきたいと思います!発表時のスライドと比べて、よりHaskellを知っている人向けになってしまいますが、regex-applicativeの魅力を明確に伝えるために必要なのでご了承ください。Applicativeスタイルを前提知識とします。tohereregex-applicativeって?regex-applicativeは、正規表現をHaskellの内部DSLとして表現したライブラリーです。名前のとおり、いわゆる「Applicativeスタイル」で正規表現を書くことができます。tohereregex-applicativeのAPI概要regex-applicativeには、正規表現オブジェクトRE型の値とマッチさせる文字列を受け取って、その結果を返す関数がいくつかあります。今回はそのうち最も単純なmatch関数を使用します。👇のような型定義となっています。a定義のとおり、RE型は型引数としてマッチさせる文字の型sと、マッチした結果にも使われる「正規表現の結果」を表す型aを受け取ります。RE型をApplicativeのインスタンスにするためには、その結果を表す型が必須なのです。この後出す例でこの「正規表現の結果」を好きな値に変える方法を示しましょう。第2引数がマッチさせる文字列に当たります。[s]とRE型の第1型引数sのリストになっているとおり、match関数(と、その他のregex-applicativeにおいて文字列をマッチさせるAPI)は任意のリストに対して使用することができます。Haskellの標準の文字列Stringの実態は[Char]、すなわちCharのリストなので、通常regex-applicativeを使用する場合sにはCharが割り当てられます。型変数なので、当然他の型のリストに対しても使用できます。これは他の正規表現ライブラリーではあまりない特性でしょう。戻り値はおなじみのMaybe型です。a型の「結果」、a型の値をJustにくるんで返します。失敗すればもちろんNothingを返します。⚠️match関数について特筆すべきことをもう一つ。他のよくある正規表現ライブラリーと異なり、match関数は完全一致じゃないとマッチしないのでご注意ください。tohereregex-applicativeの使用例それではいよいよregex-applicativeパッケージを使ってみましょう。👇のコマンドでインストールして、GHCiで試します。ghci(最近の)cabalの場合は👇を実行すればできるはずです。regex-applicativeGHCiが起動したら、こちらのimport文を張って、本記事のサンプルを実行する準備をしてください。sここからは、正規表現の基本的な機能を利用するためのregex-applicativeのAPIを紹介します。sという型定義のとおり、引数として受け取った文字と文字列における文字が等しいかチェックして、等しければマッチした文字をそのまま返す正規表現を作ります。一般化したバージョンとして、psymという関数もあります。sという型定義のとおり、「文字を受け取ってブール値を返す関数」を受け取って、受け取った関数が文字に対してTrueを返したらマッチする、という正規表現を作ります。'b'と書けば、文字クラスっぽいことができます。a正規表現に欠かせない、空文字(ε)を表す正規表現も作れます。Applicative型クラスのpureで表現します。"b"Nothingもちろん、pureは任意の値を受け取って「受け取った値をそのまま返すもの」を作ることができるので、結果として文字(列)以外の値を返す正規表現も、簡単に作ることができます。[a]続いて連接、つまり「二つ以上の正規表現を続けてマッチさせる正規表現を作る」処理です。regex-applicativeでは、Applicative型クラスの*>がそのまま連接として使えるようになっています。'b'当然、単なる文字の正規表現を並べることはありふれたことなので、string関数という文字列を渡すだけのバージョンも用意されています。"ab"さらに、regex-applicativeの正規表現オブジェクトはIsString型クラスのインスタンスでもあるので、OverloadedStrings言語拡張を使えば文字列リテラルだけで正規表現オブジェクトを作ることができます。a正規表現の「選択」、すなわち「二つの正規表現のうちどちらか一方にマッチする正規表現を作る」処理は、Alternative型クラスでおなじみの<|>を使います1。[a]正規表現の「繰り返し」、指定した正規表現を繰り返しマッチさせる正規表現を作る処理は、これまたAlternativeのmanyメソッド・someメソッドによって実装されています。Alternative型クラスのデフォルトの定義どおり、manyが0回以上の繰り返し、someが1回以上の繰り返しを表しています。a)それから、いわゆる「正規表現の基本三演算」には含まれてませんが(選択とpureで実装できるので)、この後の例で使用するので「オプショナルなマッチ」を実現する方法を紹介しておきます。名前のとおりoptionalという関数を使います。tohereマッチした結果をHaskellの値に割り当てここからは、他の正規表現ライブラリーでは珍しい、「正規表現でマッチした結果をHaskellの値に割り当てる方法」をより詳しく紹介します。tohere組み込みの正規表現を使う例えば、Text.Regex.Applicative.Commonモジュールにあるdigitは、一桁の数字(つまり0から9)にマッチした上で、結果としてマッチした値を文字ではなく、整数として返す正規表現を提供します。1加えて、先ほど紹介したmany関数と組み合わせると、マッチした結果を整数のリストとして取得することもできます。任意の(一引数の)関数を適用するregex-applicativeは、名前のとおり正規表現をApplicativeスタイルで利用できるようにするためのライブラリーです。当然ながらApplicativeスタイルに必須の<$>関数も使用できます。a型の返す「マッチした結果」に、あなたの好きな関数を適用して変換した正規表現を作れるのです。digitの例を再利用して、マッチした整数の合計値を求めてみましょう。任意の関数を適用するApplicativeスタイルのもう一つの重要な関数といえば、やっぱり<*>でしょう。digitを再利用して、「先頭に書かれた桁数だけ数字を取得する」という例を書いてみます。tohereもうちょっと複雑な例ここまで紹介した例を使用してもうちょっと複雑な例を書いてみましょう。小さな正規表現を組み合わせて、httpかhttpsのURLにおける、オリジンにマッチする正規表現を簡単に書いてみます。URLのスキームにマッチさせるために、「httpの後にオプショナルなs、続けて://」という文字列にマッチする正規表現を作ります。"://"<*を使うことで、://の部分にはマッチしてもマッチした結果は無視している点にご注意ください。regex-applicativeはこのように、「マッチしたら関数に渡す文字列」と「マッチしても関数に渡さない文字列」をユーザーが書き分けられるようになっているので、他の正規表現ライブラリーにあるようなキャプチャー2や、先読み言明・後読み言明などの機能が必要ないのです。続けて、ホスト名にマッチする正規表現を作ります。ここでは単純化して、「アルファベットの小文字かピリオド1文字以上」という文字列にしておきます。"."))最後はポート番号です。:という文字の後にText.Regex.Applicative.Commonに入ったdecimal、すなわち一桁以上の10進数にマッチする正規表現を使います。decimal以上で正規表現のパーツができました。前に、マッチした結果を割り当てるレコード型を定義します。Showあとは<$>や<*>を使って組み合わせて、Origin値コンストラクターに食わせるだけです!ポート番号はオリジンにおいてはなくても良いので、省略した場合は仮に80としておきましょう3。80)今度こそ使ってみます。tohere👍regex-applicativeのメリットregex-applicativeパッケージには、他の正規表現ライブラリーと比べて、以下のメリットがあります。tohere👎regex-applicativeのデメリット一方regex-applicativeパッケージには、他の正規表現ライブラリーに対する以下のデメリットがあります。おける正規表現エンジンの分類を参考に説明しましょう。p.56では、正規表現エンジンを次の二つに分類しています。正規表現をバイトコード(bytecode)と呼ばれるものに変換して正規表現マッチングを行うさて、regex-applicativeの場合はどちらなのでしょうか?ソースコードを読んでみると、どうやらどちらでもなさそうなことがわかります。aをNFAにcompileという関数で変換した後、DFAに変換しないでそのまま使っているからです。一般的に、NFAはDFAに変換可能で、変換してからマッチさせた方がしばしば高速にマッチできることが知られています。ところがregex-applicativeではその変換を行わず、NFAとして使用しているのです。した仕様になっているかについて、私の推測を述べましょう4。regex-applicativeでは先ほど紹介したpsym関数のように、「任意の文字を受け取る関数」を正規表現オブジェクトに含められなければなりません。結果、関数がどんな文字の時にどんな値を返すのか(マッチが成功するのかしないのか)、正規表現オブジェクトをコンパイルする関数にはわからなくなってしまうのです。効率の良いDFAの実装では、DFAの一つ一つの状態ごとに「どの文字を受け取ったら次はどの状態に遷移するか」という情報を、連想配列として持っておかなければなりません5。そのため、どの文字を受け取ったらマッチが成功するのかわからない箇所が正規表現オブジェクトに混ざっている限り、効率の良いDFAの実装にはできないのです。その分、regex-applicativeでは任意の文字を受け取る関数が使えるので、普通の正規表現ライブラリーよりも柔軟に書くことができるようになっています。その点を考慮したトレードオフなんでしょう。tohereregex-applicativeの実際の実装さらにregex-applicativeの実装を掘ってみましょう。r型の値のキューに変換します。これがregex-applicativeにおけるNFAと呼べそうですね。r型の値は、NFAにおける状態遷移を表します。r型定義のとおり、ThreadとAcceptという二通りの値をとります6。r]という関数と同等の型です。r]に文字を渡します。r型の値を(そのリストから)一つずつキューに追加して、また次の文字にマッチさせます。マッチが失敗した、ということなのです。threadId_はキューに追加する際同じthreadId_のThreadを追加してしまうのを防ぐためのキーです。rは名前のとおりNFAの受理状態を表しています。rを返したThreadのみが「マッチした」と解釈されます。r]を返す関数、すなわち「文字を受け取って次の状態のリストを返す継続」として作られています。実際に実行する際の流れを見てみると、ReObjectに含まれるThreadを一つずつ実行してみて、結果が条件に合うものを選ぶ、といった方が近いです。match関数では、ReObjectに文字を一文字ずつ与えた結果の中から、listToMaybeを使って最初にAcceptにたどり着くThreadを取得しています。それから、最長マッチする部分文字列を検索するfindLongestPrefix関数は、マッチが失敗するか残りの文字列が空になるまで繰り返し文字をReObjectに与えることで、できるだけ長いマッチが返るように調整しています。このようにregex-applicativeは、ReObject(NFA)に文字を一つずつ与えてマッチ結果を生成する処理と、そのマッチ結果を選び取る処理とを分離することで、様々な方針でマッチできるようになっているのです。tohere各種パーサーコンビネーターさて、ここまでこの文章を読んでいただけた方の中には、「これってmegaparsecとかattoparsecとかのパーサーコンビネーターライブラリーと何が違うんだ?」という疑問をお持ちの方も多いでしょう。場合、パーサーコンビネーターライブラリーも下記のような特徴を持ち合わせています。「文字(Char)」の列以外にもマッチできる特に「ApplicativeやAlternative型クラスのメソッドを利用したAPI」である点は興味深く、場合によっては、使うライブラリーだけ換えて式をコピペしてもコンパイルは通る、なんてことが普通にあり得るくらい似ています。コンパイルが通るだけでは意図通りに動くとは限りません。regex-alternativeと一般的なパーサーコンビネーターライブラリーには、「自動的にバックトラックをするかしないか」という違いがあるためです。次の式はregex-applicativeでもattoparsecでも有効な式ですが、regex-applicativeのmatch関数では、「abが1回以上繰り返される文字列」にマッチして最後のabを返すことができるのに、attoparsecのparse関数ではパースに失敗してしまいます。attoparsecした上で以下のように書いて試してみましょう。"ab"が返ってきてますね😌。input"いずれの文字列でも失敗になってしまいました。"ab"が処理できなくなってしまうためです。"ab"では、正規表現全体がマッチするよう、自動でバックトラックしてくれます。"ab"のマッチは当然失敗してしまいます。regex-applicativeはそれではあきらめません。"ab")が消費した文字を1文字ずつ返却してくれるのです。これがバックトラックです。regex-alternativeに限らず、大抵の正規表現エンジンがこのように自動的なバックトラックを行います。した性質の違いにより、regex-applicativeは文字列の中間に指定したパターンをマッチさせるのが、パーサーコンビネーターライブラリーよりも得意です。「文字列の中間にある1桁以上の10進数」にマッチさせる場合、regex-alternativeでは次のように書きます。12345fewは「控えめな繰り返し」を実現するための関数です。引数で指定した正規表現を0回以上マッチさせる、という点ではmanyと同じですが、前後にある正規表現がなるべく長くマッチするよう、優先してマッチさせてくれます。anySymは普通の正規表現ライブラリーでいうところの.*?に相当します。anyCharと書いてみても、やはりうまくいきません。anyCharがすべての文字列を消費してしまい、それ以降のdecimalなどがマッチできないためです。処理するには、「decimalの先頭以外の文字列」、すなわち「数字以外の文字列」がmanyであることを明示する方法をとるしかありません7。12345そんなわけで、regex-applicativeは、HaskellによくあるパーサーコンビネーターのようにApplicativeスタイルで書けて、なおかつ他の正規表現ライブラリーのように中間マッチがしやすいという、両方の良さを持ち合わせていると言えます。replace-attoparsec・replace-megaparsec...と、regex-applicativeのよさを語ったところで舌の根も乾かぬうちに恐縮ですが、実はattoparsecをはじめパーサーコンビネーターライブラリーの「中間マッチがやりにくい」という弱点を改善するためのパッケージがあります。replace-attoparsecやreplace-megaparsecといいます8。名前のとおりreplace-attoparsecがattoparsecを改善するパッケージで、replace-megaparsecがmegaparsecを改善するパッケージです。名前もAPIもお互いそっくりなんで(作者も同じですしね)、今回はreplace-attoparsecの方を紹介しましょう。replace-attoparsecを使えば、次のように書くだけで「文字列の中間にある1桁以上の10進数」を取り出すことができます。"def"]"abc12345def"の中間にある12345だけでなく、パースできなかったabc、defという文字列もおまけで取得できました!decimalがパースできた箇所がRightとして、パースできなかった箇所がLeftとして返却されていることに注意してください。失敗したら先頭の一文字をスキップして、次の文字からまたマッチさせてみるという処理を繰り返しています。結果的にパースできない文字列はすべてスキップして、文字列の中間にある、パースできる文字列のみにパーサーを適用できるのです。tohereまとめ以上です!👋まとめもスライドからのコピペで!regex-applicativeは、Haskellの式で正規表現を書ける内部DSLパーサーコンビネーターっぽく使えて、かつ正規表現の良さを持ち合わせている内部は「文字を受け取って続きの状態のリストを返す関数」として表現されたNFAで実装されているAlternativeは、Applicativeより強力な(できることが多い)型クラスです。いう意味で、regex-applicativeは本当は「regex-alternative」と呼んだ方が適切なのかも知れません。正確には、キャプチャーした文字列を正規表現の中で再利用することができないので、他の正規表現ライブラリーのキャプチャー機能と完全に同等のことができるわけではありません。これは現状のregex-applicativeの制限です。↩もちろん、実際のところhttpsの場合デフォルトのポート番号は443であるべきですが、ちゃんと実装しようとすると結構複雑になるのでご容赦を!↩この記事の最後の方を書いていて思い出しました。regex-applicativeはDFAベースの正規表現エンジンでは不可能な「控えめな繰り返し」をサポートしているから、という理由もあるようです。132における実装例では、これを状態と文字による二次元配列として実装しています。並行並列プログラミングで出てくるあの「スレッド」とは違うのでご注意ください。↩ただし、一般に、正規表現ライブラリーであってもこのような書き方をした方が効率よくマッチさせやすいでしょう。↩こちらの記事でも触れているとおり、かつて私も同じ目的のパッケージを作成しました。これらのパッケージの方が明らかにドキュメントが充実していて、機能も豊富なので今回はこれらを紹介します。将来的にはsubstring-parserはdeprecatedにするかも知れません。ライセンスの下に提供されています。Analyticsでアクセス情報を収集しています。集めた情報は統計的に処理した上で、当ウェブサイトの改善のための参考情報としてのみ使用します。