やったこと

マギレコ

昨日イベントアイテム集めすぎて周回が面倒。
なんで1万近く集めてるんですかね‥‥。

Scala

内側の関手がMonadかつAlternativeのときStateTにAlternativeのインスタンスを提供しているのだけど、これが内側の関手によってはAlternativeのlawを満たさないことがあることに気付いた。

具体的にはStateT[Option, Any, *]のAlternativeインスタンスはright distibutive lawを満たさない。
right distributive lawというのは(ff <+> fg) <*> fa === (ff <*> fa) <+> (fg <*> fa)というやつで、満たさない例はこんなものがある。

def guard[F[_]: Alternative](c: Boolean): F[Unit] =
  if (c) Alternative[F].pure(()) else Alternative[F].emptyK

val fa: StateT[Option, Boolean, Unit] =
  StateT.get.flatMap(guard(_))
val ff: StateT[Option, Boolean, Unit => Unit] =
  StateT.put(false).map(_ => x => x)
val fg: StateT[Option, Boolean, Unit => Unit] =
  StateT.put(true).map(_ => x => x)

つまり、

• ffは状態をfalseセットして関数を返すStateTオブジェクト
• fgは状態をtrueにセットして関数を返すStateTオブジェクト
• faは状態がtrueのとき()を返し、falsdeのときは失敗するStateTオブジェクト

このとき(ff <+> fg) <*> faを適当に実行するとNoneになるが、(ff <*> fa) <+> (fg <*> fa)はSome((true, ()))になり、一致しない。

どうしてこうなるのかというと、

• 左辺では(ff <+> fg)がffの結果になり、その後faが計算されるが、ffでは状態がfalseになっているためNoneになり
• 右辺では(ff <*> fa)がNoneになったあと(fg <*> fa)が計算されてSome((true, ()))になるため。

で、根本的な問題はOptionが値を0か1つか持てず、バックトラックの余地が無いところかな、と考えている。
なので、仮にEither[A, *]とかTry[E, *]にAlternativeのインスタンスがあったら同じような問題が起こると思う。

ただ、具体的に内側の関手がどういうときにこの問題が起きるのかを表すようなlawは知られてないっぽいし(少なくともOptionのAlternativeはright distributiveを満たしてるけど、StateTに入れるとこの問題が起きる)、StateTと同じような問題のあるモナド変換子があるのかもよく分からない。

なので、この問題への対処は、

1. StateTのAlternativeインスタンスを削除する
2. Alternativeのlawからright disributiveを除く

の2つくらいしか無いのではないかと思う。

個人的には2.が悪くない気がしている。
right distributiveを諦めるとStateTだけでなくて、IOとかParser(Parsecのやつ)みたいなのもAlternativeとして合法になるし、実際その方が有意義だと思うので。

catsの方で聞いてみたいけど英語かったるいなぁ。

参考文献: "From monoids to near-semirings: the essence of MonadPlus and Alternative" https://lirias.kuleuven.be/bitstream/123456789/499951/1/main.pdf