regex-applicative: 内部DSLとしての正規表現（ブログ記事版）

RegexFestaで発表した内容を詳しく紹介します

Posted by YAMAMOTO Yuji(@igrep) on December 30, 2019Tags: 正規表現
投稿したい方はこちら

先日、といっても2019年10月18日のことなんでもう2ヶ月以上も経ってしまいましたが、私はRegex Festaというイベントで、「regex-applicative」というパッケージの紹介を致しました。
今回はその際使用したスライドを、ブログ記事として詳しく共有させていただきたいと思います！
発表時のスライドと比べて、よりHaskellを知っている人向けになってしまいますが、regex-applicativeの魅力を明確に伝えるために必要なのでご了承ください。
Applicativeスタイルを前提知識とします。

Link to
hereはじめにまとめ

  • regex-applicativeは、Haskellの式で正規表現を書ける内部DSL
  • パーサーコンビネーターっぽく使えて、かつ正規表現の良さ — 中間マッチが簡単にできる点など — を持ち合わせている
  • 内部は「文字を受け取って続きの状態のリストを返す関数」として表現されたNFAで実装されている

Link to
hereregex-applicativeって？

regex-applicativeは、正規表現をHaskellの内部DSLとして表現したライブラリーです。
名前のとおり、いわゆる「Applicativeスタイル」で正規表現を書くことができます。

Link to
hereregex-applicativeのAPI概要

regex-applicativeには、正規表現オブジェクトRE型の値とマッチさせる文字列を受け取って、その結果を返す関数がいくつかあります。
今回はそのうち最も単純なmatch関数を使用します。👇のような型定義となっています。

match :: RE s a -> [s] -> Maybe a

定義のとおり、RE型は型引数としてマッチさせる文字の型sと、マッチした結果にも使われる「正規表現の結果」を表す型aを受け取ります。
RE型をApplicativeのインスタンスにするためには、その結果を表す型が必須なのです。この後出す例でこの「正規表現の結果」を好きな値に変える方法を示しましょう。

そして第2引数がマッチさせる文字列に当たります。[s]とRE型の第1型引数sのリストになっているとおり、match関数（と、その他のregex-applicativeにおいて文字列をマッチさせるAPI）は任意のリストに対して使用することができます。
Haskellの標準の文字列Stringの実態は[Char]、すなわちCharのリストなので、通常regex-applicativeを使用する場合sにはCharが割り当てられます。
型変数なので、当然他の型のリストに対しても使用できます。これは他の正規表現ライブラリーではあまりない特性でしょう。

戻り値はおなじみのMaybe型です。マッチが成功すれば、引数に渡した正規表現RE s a型の「結果」、a型の値をJustにくるんで返します。そして失敗すればもちろんNothingを返します。

⚠️match関数について特筆すべきことをもう一つ。他のよくある正規表現ライブラリーと異なり、match関数は完全一致じゃないとマッチしないのでご注意ください。
regex-applicativeには完全一致じゃないといけない関数と完全一致じゃなくてもよい関数両方があるので、少し混乱します😰

Link to
hereregex-applicativeの使用例

それではいよいよregex-applicativeパッケージを使ってみましょう。
👇のコマンドでインストールして、GHCiで試します。

stack build regex-applicative
stack exec ghci

（最近の）cabalの場合は👇を実行すればできるはずです。

cabal v2-install --lib regex-applicative
cabal v2-repl -b regex-applicative

GHCiが起動したら、こちらのimport文を張って、本記事のサンプルを実行する準備をしてください。

import Text.Regex.Applicative
import Text.Regex.Applicative.Common

Link to
hereただの文字: sym :: Eq s => s -> RE s s

ここからは、正規表現の基本的な機能を利用するためのregex-applicativeのAPIを紹介します。
まずはただの文字一つにマッチするsymから:

> match (sym 'a') "a"
Just 'a'

> match (sym 'a') "b"
Nothing

sym :: Eq s => s -> RE s sという型定義のとおり、引数として受け取った文字と文字列における文字が等しいかチェックして、等しければマッチした文字をそのまま返す正規表現を作ります。

また、より一般化したバージョンとして、psymという関数もあります。
こちらはpsym :: (s -> Bool) -> RE s sという型定義のとおり、「文字を受け取ってブール値を返す関数」を受け取って、受け取った関数が文字に対してTrueを返したらマッチする、という正規表現を作ります。

なので例えば、

> match (psym (== 'a')) "a"

と書けばsym関数と全く同じことができますし、

> match (psym (`elem` "abcdef")) "a"
Just 'a'
> match (psym (`elem` "abcdef")) "b"
Just 'b'

と書けば、文字クラスっぽいことができます。

Link to
here空文字（ε）: pure :: a -> RE s a

正規表現に欠かせない、空文字（ε）を表す正規表現も作れます。
Applicative型クラスのpureで表現します。

> match (pure 'a') ""
Just 'a'
> match (pure 'a') "b"
Nothing

もちろん、pureは任意の値を受け取って「受け取った値をそのまま返すもの」を作ることができるので、結果として文字（列）以外の値を返す正規表現も、簡単に作ることができます。

> match (pure True) ""
Just True
> match (pure 42) ""
Just 42

Link to
here連接: (*>) :: RE s a -> RE s b -> RE s b・string :: Eq a => [a] -> RE a [a]

続いて連接、つまり「二つ以上の正規表現を続けてマッチさせる正規表現を作る」処理です。
regex-applicativeでは、Applicative型クラスの*>がそのまま連接として使えるようになっています。

> match (sym 'a' *> sym 'b') "ab"
Just 'b'

当然、単なる文字の正規表現を並べることはありふれたことなので、string関数という文字列を渡すだけのバージョンも用意されています。

-- マッチする文字列は同じ、より分かりやすいバージョン
> match (string "ab") "ab"
Just "ab"

さらに、regex-applicativeの正規表現オブジェクトはIsString型クラスのインスタンスでもあるので、OverloadedStrings言語拡張を使えば文字列リテラルだけで正規表現オブジェクトを作ることができます。

> :set -XOverloadedStrings
> match "ab" "ab"
Just "ab"

Link to
here選択: (<|>) :: RE s a -> RE s a -> RE s a

正規表現の「選択」、すなわち「二つの正規表現のうちどちらか一方にマッチする正規表現を作る」処理は、Alternative型クラスでおなじみの<|>を使います1。

> match (sym 'a' <|> sym 'b') "a"
Just 'a'
> match (sym 'a' <|> sym 'b') "b"
Just 'b'

Link to
here繰り返し: many :: RE s a -> RE s [a]・some :: RE s a -> RE s [a]

正規表現の「繰り返し」、指定した正規表現を繰り返しマッチさせる正規表現を作る処理は、これまたAlternativeのmanyメソッド・someメソッドによって実装されています。
Alternative型クラスのデフォルトの定義どおり、manyが0回以上の繰り返し、someが1回以上の繰り返しを表しています。

> match (many (sym 'a')) "aaaaaaaaaa"
Just "aaaaaaaaaa"
> match (some (sym 'a')) "aaaaaaaaaa"
Just "aaaaaaaaaa"

> match (many (sym 'a')) ""
Just ""
> match (some (sym 'a')) ""
Nothing

Link to
hereオプショナルなマッチ: optional :: RE s a -> RE s (Maybe a)

それから、いわゆる「正規表現の基本三演算」には含まれてませんが（選択とpureで実装できるので）、この後の例で使用するので「オプショナルなマッチ」を実現する方法を紹介しておきます。
名前のとおりoptionalという関数を使います。これもAlternative型クラスに対して使える関数ですね！

> match (sym 'a' *> optional (sym 'b')) "ab"
Just (Just 'b')
> match (sym 'a' *> optional (sym 'b')) "a"
Just Nothing

Link to
hereマッチした結果をHaskellの値に割り当て

ここからは、他の正規表現ライブラリーでは珍しい、「正規表現でマッチした結果をHaskellの値に割り当てる方法」をより詳しく紹介します。

Link to
here組み込みの正規表現を使う

例えば、Text.Regex.Applicative.Commonモジュールにあるdigitは、一桁の数字（つまり0から9）にマッチした上で、結果としてマッチした値を文字ではなく、整数として返す正規表現を提供します。

> match digit "1"
Just 1

加えて、先ほど紹介したmany関数と組み合わせると、マッチした結果を整数のリストとして取得することもできます。

> match (many digit) "12345"
Just [1,2,3,4,5]

Link to
here(<$>) :: (a -> b) -> RE s a -> RE s b: 任意の（一引数の）関数を適用する

regex-applicativeは、名前のとおり正規表現をApplicativeスタイルで利用できるようにするためのライブラリーです。
当然ながらApplicativeスタイルに必須の<$>関数も使用できます。
正規表現オブジェクトRE s a型の返す「マッチした結果」に、あなたの好きな関数を適用して変換した正規表現を作れるのです。

先ほどのmany digitの例を再利用して、マッチした整数の合計値を求めてみましょう。

> match (sum <$> many digit) "12345"
Just 15

Link to
here(<*>) :: RE s (a -> b) -> RE s a -> RE s b: 任意の関数を適用する

Applicativeスタイルのもう一つの重要な関数といえば、やっぱり<*>でしょう。
many digitを再利用して、「先頭に書かれた桁数だけ数字を取得する」という例を書いてみます。

> match (take <$> digit <*> many digit) "312345"
Just [1,2,3]

Link to
hereもうちょっと複雑な例

ここまで紹介した例を使用してもうちょっと複雑な例を書いてみましょう。
小さな正規表現を組み合わせて、httpかhttpsのURLにおける、オリジンにマッチする正規表現を簡単に書いてみます。

まずは部品作りです。

URLのスキームにマッチさせるために、「httpの後にオプショナルなs、続けて://」という文字列にマッチする正規表現を作ります。

> schemeRe =
    ((++) <$> string "http" <*> (string "s" <|> pure ""))
      <* string "://"

<*を使うことで、://の部分にはマッチしてもマッチした結果は無視している点にご注意ください。
regex-applicativeはこのように、「マッチしたら関数に渡す文字列」と「マッチしても関数に渡さない文字列」をユーザーが書き分けられるようになっているので、他の正規表現ライブラリーにあるようなキャプチャー2や、先読み言明・後読み言明などの機能が必要ないのです。

続けて、ホスト名にマッチする正規表現を作ります。
ここでは単純化して、「アルファベットの小文字かピリオド1文字以上」という文字列にしておきます。

> hostRe = some (psym (`elem` ['a'..'z'] ++ "."))

最後はポート番号です。
:という文字の後にText.Regex.Applicative.Commonに入ったdecimal、すなわち一桁以上の10進数にマッチする正規表現を使います。

> portRe = sym ':' *> decimal

以上で正規表現のパーツができました。
早速使ってみる… 前に、マッチした結果を割り当てるレコード型を定義します。

data Origin =
  Origin { scheme :: String, host :: String, port :: Int }
  deriving Show

あとは<$>や<*>を使って組み合わせて、Origin値コンストラクターに食わせるだけです！
ポート番号はオリジンにおいてはなくても良いので、省略した場合は仮に80としておきましょう3。

originRe = Origin   <$>
           schemeRe <*>
           hostRe   <*>
           (portRe <|> pure 80)

今度こそ使ってみます。

> match originRe "https://example.com:8080"
Just (Origin {scheme = "https", host = "example.com", port = 8080})
> match originRe "http://example.com"
Just (Origin {scheme = "http", host = "example.com", port = 80})

regex-applicativeを使うことで、URLのオリジンにマッチさせるだけでなく、マッチした結果をOrigin型の値として割り当てる正規表現が作れました！🎉

Link to
here👍regex-applicativeのメリット

regex-applicativeパッケージには、他の正規表現ライブラリーと比べて、以下のメリットがあります。

  • 文字列以外の扱いにも強い
    • マッチした結果から（文字列以外の）Haskellの値に割り当てるのが簡単！
      • 「生のデータ」からアプリケーションにおける「コアの処理が欲しいデータ」への変換がワンストップ
    • 文字列だけでなく、任意のリストに対してマッチできる
  • 内部DSLとして書けるので、コンパイラーによる型チェックの恩恵を受けやすい
    • 前述の「マッチした結果から（文字列以外の）Haskellの値に割り当てる」処理も、すべて型チェックされる

Link to
here👎regex-applicativeのデメリット

一方regex-applicativeパッケージには、他の正規表現ライブラリーに対する以下のデメリットがあります。

  • コードは長い
    • 内部DSLなのでやむなし
    • 専用のメタキャラクターより分かりやすい、とも言える
  • ユーザーからの入力として、正規表現を受け取ることは難しい
    • これも内部DSLなのでやむなし
  • おそらくCとかで書いたものほど速くはない
    • そんなに細かい最適化をしているわけではないし、Pure Haskellなので…
  • String以外の文字列にはマッチできない…

Link to
here⚙️regex-applicativeの仕組み

ここからは、regex-applicativeにおける正規表現エンジンがどのように作られているか、『正規表現技術入門』における正規表現エンジンの分類を参考に説明しましょう。

Link to
here📑正規表現エンジンの分類

『正規表現技術入門』のp.56では、正規表現エンジンを次の二つに分類しています。

  • DFA型
    • 正規表現を決定性有限オートマトン（deterministic finite automaton）と呼ばれるものに変換して正規表現マッチングを行う
  • VM型
    • 正規表現をバイトコード（bytecode）と呼ばれるものに変換して正規表現マッチングを行う

さて、regex-applicativeの場合はどちらなのでしょうか？
ソースコードを読んでみると、どうやらどちらでもなさそうなことがわかります。
というのも、正規表現オブジェクトRE s aをNFAにcompileという関数で変換した後、DFAに変換しないでそのまま使っているからです。
一般的に、NFAはDFAに変換可能で、変換してからマッチさせた方がしばしば高速にマッチできることが知られています。
ところがregex-applicativeではその変換を行わず、NFAとして使用しているのです。

なぜそうした仕様になっているかについて、私の推測を述べましょう4。
regex-applicativeでは先ほど紹介したpsym関数のように、「任意の文字を受け取る関数」を正規表現オブジェクトに含められなければなりません。
結果、関数がどんな文字の時にどんな値を返すのか（マッチが成功するのかしないのか）、正規表現オブジェクトをコンパイルする関数にはわからなくなってしまうのです。
一方、効率の良いDFAの実装では、DFAの一つ一つの状態ごとに「どの文字を受け取ったら次はどの状態に遷移するか」という情報を、連想配列として持っておかなければなりません5。
そのため、どの文字を受け取ったらマッチが成功するのかわからない箇所が正規表現オブジェクトに混ざっている限り、効率の良いDFAの実装にはできないのです。

その分、regex-applicativeでは任意の文字を受け取る関数が使えるので、普通の正規表現ライブラリーよりも柔軟に書くことができるようになっています。
その点を考慮したトレードオフなんでしょう。

Link to
hereregex-applicativeの実際の実装

さらにregex-applicativeの実装を掘ってみましょう。
先ほど紹介したcompile関数は、正規表現オブジェクトRE s aをReObject s rという型の、Thread s r型の値のキューに変換します。
これがregex-applicativeにおけるNFAと呼べそうですね。

newtype ReObject s r = ReObject (SQ.StateQueue (Thread s r))

Thread s r型の値は、NFAにおける状態遷移を表します。

data Thread s r
    = Thread
        { threadId_ :: ThreadId
        , _threadCont :: s -> [Thread s r]
        }
    | Accept r

型定義のとおり、ThreadとAcceptという二通りの値をとります6。

  • ⏩Threadはその用途からして、事実上s -> [Thread s r]という関数と同等の型です。regex-applicativeはReObjectによって文字列[s]の値をマッチさせる際、このs -> [Thread s r]に文字を渡します。
    • ➡️そして、関数が結果として返した、Thread s r型の値を（そのリストから）一つずつキューに追加して、また次の文字にマッチさせます。
    • ↩︎️一方、関数が空リストを返した場合は — そう、マッチが失敗した、ということなのです。その場合は、キューからさらにThread s rの値を取り出して（値コンストラクターがThreadであれば）マッチしなかった文字をまたs -> [Thread s r]に渡します。
    • なお、threadId_はキューに追加する際同じthreadId_のThreadを追加してしまうのを防ぐためのキーです。詳細は割愛します。
  • ✅Accept rは名前のとおりNFAの受理状態を表しています。s -> [Thread s r]を繰り返し適用して最終的にAccept rを返したThreadのみが「マッチした」と解釈されます。

このように、regex-applicativeにおけるNFAはs -> [Thread s r]を返す関数、すなわち「文字を受け取って次の状態のリストを返す継続」として作られています。

ただ実際に実行する際の流れを見てみると、ReObjectに含まれるThreadを一つずつ実行してみて、結果が条件に合うものを選ぶ、といった方が近いです。
例えばmatch関数では、ReObjectに文字を一文字ずつ与えた結果の中から、listToMaybeを使って最初にAcceptにたどり着くThreadを取得しています。
それから、最長マッチする部分文字列を検索するfindLongestPrefix関数は、マッチが失敗するか残りの文字列が空になるまで繰り返し文字をReObjectに与えることで、できるだけ長いマッチが返るように調整しています。
このようにregex-applicativeは、ReObject(NFA)に文字を一つずつ与えてマッチ結果を生成する処理と、そのマッチ結果を選び取る処理とを分離することで、様々な方針でマッチできるようになっているのです。

Link to
here類似のライブラリーとの比較を軽く

Link to
here各種パーサーコンビネーター

さて、ここまでこの文章を読んでいただけた方の中には、「これってmegaparsecとかattoparsecとかのパーサーコンビネーターライブラリーと何が違うんだ？」という疑問をお持ちの方も多いでしょう。
そう、大抵の場合、パーサーコンビネーターライブラリーも下記のような特徴を持ち合わせています。

  • Haskellの内部DSLとして実装されている
    • ApplicativeやAlternative型クラスのメソッドを利用したAPI
  • マッチした結果から（文字列以外の）Haskellの値に割り当てるのが簡単
  • 「文字(Char)」の列以外にもマッチできる

特に「ApplicativeやAlternative型クラスのメソッドを利用したAPI」である点は興味深く、場合によっては、使うライブラリーだけ換えて式をコピペしてもコンパイルは通る、なんてことが普通にあり得るくらい似ています。
ただし、当然コンパイルが通るだけでは意図通りに動くとは限りません。
regex-alternativeと一般的なパーサーコンビネーターライブラリーには、「自動的にバックトラックをするかしないか」という違いがあるためです。

例えば、次の式はregex-applicativeでもattoparsecでも有効な式ですが、regex-applicativeのmatch関数では、「abが1回以上繰り返される文字列」にマッチして最後のabを返すことができるのに、attoparsecのparse関数ではパースに失敗してしまいます。

many (string "ab") *> string "ab"

stack build regex-applicative attoparsecした上で以下のように書いて試してみましょう。
まずはregex-applicativeで試す場合:

> import Text.Regex.Applicative

> match (many (string "ab") *> string "ab") "abab"
Just "ab"

> match (many (string "ab") *> string "ab") "ab"
Just "ab"

> match (many (string "ab") *> string "ab") "ababab"
Just "ab"

いずれの文字列でもJust "ab"が返ってきてますね😌。

続いてattoparsecで試す場合:

-- attoparsecは`String`をサポートしてないのでOverloadedStringsでTextとして扱う
> :set -XOverloadedStrings

> import Control.Applicative
> import Data.Attoparsec.Text

-- 文字列の終端であることを明確にするために、空文字列をfeedしておく
> feed (parse (many (string "ab") *> string "ab") "abab") ""
Fail "" [] "not enough input"

> feed (parse (many (string "ab") *> string "ab") "ab") ""
Fail "" [] "not enough input"

> feed (parse (many (string "ab") *> string "ab") "ababab") ""
Fail "" [] "not enough input"

いずれの文字列でも失敗になってしまいました。なぜうまくいかないのでしょう？
それは文字列"ababab"におけるabを、many (string "ab")が消費してしまい、*>の右辺に書いたstring "ab"が処理できなくなってしまうためです。
対するregex-applicativeにおけるmany (string "ab") *> string "ab"では、正規表現全体がマッチするよう、自動でバックトラックしてくれます。
regex-applicativeでも最初にmany (string "ab")が"ababab"全体を消費した直後では、*>の右辺に書いたstring "ab"のマッチは当然失敗してしまいます。
しかし、regex-applicativeはそれではあきらめません。*>の右辺に書いたstring "ab"が成功するまで、失敗する度にmany (string "ab")が消費した文字を1文字ずつ返却してくれるのです。これがバックトラックです。
regex-alternativeに限らず、大抵の正規表現エンジンがこのように自動的なバックトラックを行います。

こうした性質の違いにより、regex-applicativeは文字列の中間に指定したパターンをマッチさせるのが、パーサーコンビネーターライブラリーよりも得意です。

例えば「文字列の中間にある1桁以上の10進数」にマッチさせる場合、regex-alternativeでは次のように書きます。

> import Text.Regex.Applicative.Common
> match (few anySym *> decimal <* few anySym) "abc12345def"
Just 12345

fewは「控えめな繰り返し」を実現するための関数です。引数で指定した正規表現を0回以上マッチさせる、という点ではmanyと同じですが、前後にある正規表現がなるべく長くマッチするよう、優先してマッチさせてくれます。
few anySymは普通の正規表現ライブラリーでいうところの.*?に相当します。

同じことをattoparsecで実現するためにmany anyChar *> decimal <* many anyCharと書いてみても、やはりうまくいきません。

> import Data.Attoparsec.Text

> feed (parse (many anyChar *> decimal <* many anyChar) "abc12345def") ""
Fail "" [] "not enough input"

理由は先ほどと同様で、最初に書いたmany anyCharがすべての文字列を消費してしまい、それ以降のdecimalなどがマッチできないためです。
正しく処理するには、「decimalの先頭以外の文字列」、すなわち「数字以外の文字列」がmanyであることを明示する方法をとるしかありません7。

> import Data.Char

> nonDigits = many (satisfy (not . isDigit))
> feed ((parse (nonDigits *> decimal <* nonDigits)) "abc12345def") ""
Done "" 12345

そんなわけで、regex-applicativeは、HaskellによくあるパーサーコンビネーターのようにApplicativeスタイルで書けて、なおかつ他の正規表現ライブラリーのように中間マッチがしやすいという、両方の良さを持ち合わせていると言えます。

Link to
here番外編: 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進数」を取り出すことができます。

import Replace.Attoparsec.Text

> feed (parse (sepCap decimal) "abc12345def") ""
Done "" [Left "abc",Right 12345,Left "def"]

"abc12345def"の中間にある12345だけでなく、パースできなかったabc、defという文字列もおまけで取得できました！
decimalがパースできた箇所がRightとして、パースできなかった箇所がLeftとして返却されていることに注意してください。

replace-attoparsecのsepCap（「Separate and Capture」の略だそうです）は、引数として受け取ったパーサーを、

  1. とりあえず先頭からマッチさせてみて、
  2. 失敗したら先頭の一文字をスキップして、次の文字からまたマッチさせてみる

という処理を繰り返しています。
結果的にパースできない文字列はすべてスキップして、文字列の中間にある、パースできる文字列のみにパーサーを適用できるのです。

Link to
hereVerbalExpressions

そろそろ力尽きてきたのでここからはスライドのコピペで失礼します…🙏

Link to
hereまとめ

以上です！👋
まとめもスライドからのコピペで！

  • regex-applicativeは、Haskellの式で正規表現を書ける内部DSL
  • パーサーコンビネーターっぽく使えて、かつ正規表現の良さを持ち合わせている
  • 内部は「文字を受け取って続きの状態のリストを返す関数」として表現されたNFAで実装されている

  1. Alternativeは、Applicativeより強力な（できることが多い）型クラスです。そういう意味で、regex-applicativeは本当は「regex-alternative」と呼んだ方が適切なのかも知れません。↩︎

  2. 正確には、キャプチャーした文字列を正規表現の中で再利用することができないので、他の正規表現ライブラリーのキャプチャー機能と完全に同等のことができるわけではありません。これは現状のregex-applicativeの制限です。↩︎

  3. もちろん、実際のところhttpsの場合デフォルトのポート番号は443であるべきですが、ちゃんと実装しようとすると結構複雑になるのでご容赦を！↩︎

  4. この記事の最後の方を書いていて思い出しました。regex-applicativeはDFAベースの正規表現エンジンでは不可能な「控えめな繰り返し」をサポートしているから、という理由もあるようです。なぜDFAベースでは「控えめな繰り返し」ができないかは私もうまく説明できません…。↩︎

  5. 『正規表現技術入門』のp. 132における実装例では、これを状態と文字による二次元配列として実装しています。↩︎

  6. 並行並列プログラミングで出てくるあの「スレッド」とは違うのでご注意ください。↩︎

  7. ただし、一般に、正規表現ライブラリーであってもこのような書き方をした方が効率よくマッチさせやすいでしょう。↩︎

  8. こちらの記事でも触れているとおり、かつて私も同じ目的のパッケージを作成しました。しかし、これらのパッケージの方が明らかにドキュメントが充実していて、機能も豊富なので今回はこれらを紹介します。将来的にはsubstring-parserはdeprecatedにするかも知れません。↩︎

リベンジ・オブ・毎時更新 Haskell Antenna
トップに戻る
日本語をshowしてうまく表示されなかったら