必要なこと

• Haskellがある程度読み書きできる
• モナド変換子を使ったコードが書ける

不要なこと

• モナド変換子を理解している(私も本当に理解しているか怪しい)
• 自然言語処理の知識

AlternativeとMonadPlusの有用性

型クラス、 Alternative は便利です。最近の実務ではRIOがemptyをexportしないので、面倒なのでmzeroを使ってAlternativeにMonadの制約を付け加えたMonadPlusが型制約になってしまうことが多いですが。

この型クラスの具体的なインスタンスにはMaybe, [], そしてLogicTがありますが、話を簡単にするためにとりあえずMaybeで話を進めます。

Alternativeをパッと見ると、

Prelude Control.Applicative> Nothing <|> Just 1 <|> Just 2
Just 1

とかが出てきて、そんなことは退屈だし、 Monoidを使う場合などと比べてちょっと短く書けるのは良いけど、他のnull不安全な言語で||で書くとか、 Swiftで??とか書くのと同じではないか? Haskellで自分で面倒を作り出して自分で解決しているマッチポンプだ。などと言うことを思うかもしれません。

しかしこれが言語機能ではなく関数で実現されているのにも利点があります。

例えば、

choose :: Alternative f => [a] -> f a
choose = foldr ((<|>) . pure) empty

https://www.stackage.org/haddock/nightly-2022-12-07/logict-0.8.0.0/Control-Monad-Logic-Class.html#v:once

のようにListをAlternativeな汎用的なものに変換する処理が自然に合成できたりすることですね。これでListをLogicTに変換したりすることが出来ます。

またプリミティブに一つの型のみに対象を限定することなく型クラスの関数であることで拡張性を確保出来るので、後述のようにStateTなどのモナド変換子などと組み合わせることが出来て非常に便利です。 MegaparsecやattoparsecのParser型もAlternativeのインスタンスであることでAlternativeに対する汎用的な関数を使うことが出来ます。実際attoparsecパッケージで定義してある汎用的なAlternative関数が使いたいがために、 attoparsec本体を使わないのに依存してしまうことがたまにあります。

many :: Alternative f => f a -> f [a]もControl.Applicative本体に定義されてある標準の関数ですが、とても汎用的で便利です。

manyの便利性をStateを使わずに説明しようとしましたが、 MaybeT IOとか余計にややこしいのでStateの説明に行きます。 Alternative単体で便利な例を考えると「それListのMonad機能だけでで良くない?」ってなってしまったので、 AlternativeはMonadPlusにしてモナド変換子などを使うと輝いて見えるタイプの型クラスなのかもしれません。

なお言語機能じゃないから短絡評価にならないとかはHaskellは遅延評価なので基本的には問題ないです。

少し脱線すると、 Scala Catsでは、 Alternative のcombineKとかは値渡しです。なんで名前渡しにしてないんだろう…不便…ってScala書いてる時に思ってて、名前渡しにするラッパーを作っていました。 Eval とかで自分で制御しろってことなんでしょうか、でも、 scala.Option のgetOrElseはちゃんと名前呼び出しだし、実用性を重視してほしい。

Stateの有用性

何故純粋関数型言語のHaskellでわざわざStateを使うのかは過去に書いたことがあります。 HaskellのStateの必要性が, プログラミング言語の処理系を書いた時にわかったので, Stateの良さを語ります - ncaq

昔の記事では既にASTを構築してから実行する時の優位性を書いていますが、パース段階では特にStateは有用です。ソースがリストだろうがツリーだろうが、パースしたものとその残りははっきりと区別する必要があります。

特に入力元をツリーとする場合は、パースしてない残りを表す場合ために、 TextのようにIntなどでカーソル位置を表すわけにもいけないので、ツリー自体を持って、それを削っていくような実装が自然でしょう。

また一時的にサブツリーをトップレベルにしてコンビネータを実行して解析してもらうことで問題を分割することが出来ます。 Zipperに似てますね。

我々はMwbTreeという独自のツリーと、それを補助するwithLogicNewRootのような関数を作り、一時的にサブツリーを全体状態に変えコンビネータを実行して解析結果を手に入れ、サブツリーは抹消する方法を使っています。

そのうちこのツリーと関連関数をFLOSSとして配布したいなあと思っています。

よって現在のStateは自由自在に変えられて、なおかつ過去の履歴が残ると都合が良いわけです。

MonadPlusとStateを組み合わせてトイコンビネータを作る

StateTと組み合わせることでAlternativeとMonadPlusの良さが発揮されます。

極めて単純化した説明をします。

トイコンビネータを作りましょう。

例えば、

import           Control.Applicative
import           Control.Monad
import           Control.Monad.Trans.State.Strict
import           Data.Char
import           Data.Text as T

type Parser = StateT [Text] Maybe

-- | 先頭の単語を取得する。
popToken :: Parser Text
popToken = do
  s <- get
  case s of
    [] -> mzero
    (x : xs) -> do
      put xs
      return x

parseDigitOrAlpha :: Parser Text
parseDigitOrAlpha = digit <|> alpha

digit :: Parser Text
digit = do
  t <- popToken
  guard $ T.all isDigit t
  return t

alpha :: Parser Text
alpha = do
  t <- popToken
  guard $ T.all isAlpha t
  return t

のようなパーサがあるとします。

このパーサに["a"]を食わせてみましょう。

λ> runStateT parseDigitOrAlpha ["a"]
Just ("a",[])

のような結果になります。最初にdigitでtokenを消費したように見えるのに、 alphaでtokenを取得できています。

バックトラックが発生しています。

これはStateTのAlternativeの実装を見れば一目瞭然です。

 StateT m <|> StateT n = StateT $ \ s -> m s `mplus` n s

https://www.stackage.org/haddock/lts-20.3/transformers-0.5.6.2/src/Control.Monad.Trans.State.Strict.html#line-212

2つのコンビネータにその時点での状態引数を2つに分けて渡しています。 Stateの持つ状態が可変に見えても実態は不変であるからこそ出来る技ですね。不変参照のためパフォーマンスの多大な問題にはなりません。多分。

これにより他のコンビネータで状態がぐちゃぐちゃになってわけわからんと泣きながらプリントデバッグをする必要が少し減ります。

やっとmanyの有用性を示すことが出来ます。

λ> runStateT parseDigitOrAlpha ["a", "0", "b"]
Just ("a",["0","b"])
λ> runStateT (many parseDigitOrAlpha) ["a", "0", "b"]
Just (["a","0","b"],[])

のようにmanyとコンビネータを修飾してやるだけで繰り返しを表現できて汎用性もあります。 someなら空リストは許さず一つの要素を要求するとか、そういうAlternative向けの汎用関数は他にも色々あります。 Data.Attoparsec.ByteString あたりから引っ張ってきても良いかもしれませんね。これが使えるならだいたいAttoparsecそのまま使っても良いんですが… とりあえず自前のwithLogicNewRootとその派生にmanyとsomeは便利に使えてます。

ちなみにこれ、後述するLogicTでは、

StateT (MwbTree word) Logic

のような入れ子になっている必要があります。

LogicT (State (MwbTree word))

のような入れ子になっているとStateが共有されてしまいます。

これはMegaparsecでは注意が必要です。 tryコンビネータをコンビネータに付与してやらないとこのような動作にはならないことがあります。そもそもpopTokenのような雑な実装ではなく条件付きで取得していれば消費も起きないので次のAlternative要素を選ぶこともありますが。パフォーマンスを追求するためにこのような設計になっているようです。

我々は前処理でニューラルなもっと重い処理をしているのと、後処理でメチャクチャ計算負荷のかかるアルゴリズムを回しているのと、まだまだ開発途中なので今最適化を気にしても仕方ないと早すぎる最適化を危惧して、今のところあまり気にしていません。

ただこういう雑オートマトンを使う時は純粋関数で済んでも別スレッドに処理を移して、タイムアウトを設定しておいた方が良いでしょう。雑に無限再帰が発生するかもしれませんし、手軽にバックトラックしているのでReDoSみたいな問題が発生するかもしれません。 ReDoSから学ぶ，正規表現の脆弱性について - Qiita

MaybeよりListになっていると便利

先程の簡単なトイコンビネータではパーサの返り値をMaybeにしていましたが、特に結果が一意に定まらない可能性が高い自然言語処理ではListの方が便利なこともあります。

パーサの型を以下のように変更するだけで、

type Parser = StateT [Text] []

実行結果ではソースの取得数などがブレにブレてくれます。

λ> runStateT (many parseDigitOrAlpha) ["a", "0", "b"]
[(["a","0","b"],[]),(["a","0"],["b"]),(["a"],["0","b"]),([],["a","0","b"])]

これだけ見るとなんの役に経つんだという感じがしなくは無いですが、いわゆるNN NN問題(複合名詞の区切りがどこなのかイマイチ分からない)とかを、仕方ないので両方の解析結果を返すということがお手軽に出来ます。

もちろん結果は大量になるのでtakeなどで区切る必要がありますね。

2022-12-24追記: 作った

とりあえず実装しました。 feat!: instance MonadLogic for WriterT by ncaq · Pull Request #33 · Bodigrim/logict mtlのバージョン要求を引き上げているため本家に取り込まれるのかはまだ謎ですが。