本物のFree MonadPlus？

scalaz haskell

「もう一度来てください。本物のFree MonadPlusを見せてあげますよ」
そう言い残してScalaちゃんは去っていった・・・。


というわけで(どういうわけだよ！)
本物のFree Monadって存在したのか！？っていうメモを書いておきたいと思います。
いや、実は知ってる人にとっては常識だったのかよくわかりませんが、自分は知らなかったので。
(というかekmett/freeにないなら、そもそも不可能なのではないか？くらいに思ってた)


"本物の" とはどういうことか？というと、偽者(MonadPlus則を満たさない)が以前 ekmett/free の内部に存在して、自分が指摘したら消えてしまった事件(?)があったのです。

issue報告したらFree MonadPlusが消えた

さて、それでなんとなく寝起きでtwitterで流れてきた"ある論文"を読んでいたら、Free MonadPlusがさらっと出てきてるではありませんか！


http://www.fceia.unr.edu.ar/~mauro/pubs/smartviews/smartviews.pdf


以下該当部分のコード引用

data FMP f x = FNil
  | ConsV x (FMP f x )
  | ConsF (f (FMP f x )) (FMP f x )


instance Functor f ⇒ Monad (FMP f ) where
  return x = ConsV x FNil
  FNil >>= f = FNil
  (ConsV x v) >>= f = f x ‘mplus‘ (v >>= f )
  (ConsF t v) >>= f = ConsF (fmap (>>=f ) t) (v >>= f )


instance MonadPlus (FMP f ) where
  mzero = FNil
  FNil ‘mplus‘ y = y
  (ConsV x y) ‘mplus‘ z = ConsV x (y ‘mplus‘ z )
  (ConsF x y) ‘mplus‘ z = ConsF x (y ‘mplus‘ z )


この論文自体は「reflection without remorse」のような話？(まだ全部読んでないのでよくわかってない)で、上記のFree MonadPlus以外の別の形のFree MonadPlusがでてきたり、(Plusじゃない普通の)Free MonadやList MonadTransformerの話がでてきます。

で、Haskellコードがあったら無意識のうちに手が動いてScalaに翻訳するのは当然ですよね？
というわけで気がついたら翻訳されたScalaコードが目の前にありました。scalapropsによるMonadPlus則のテストもあった、素晴らしい。

以前 ekmett/free にあったFree MonadPlusは明らかにMonadPlus則満たさなかったですが、これはscalapropsのテスト通ったので、満たしそうな予感がします。

ところで、論文内にあった別の(効率がいい？)形でも実装したんですが

https://gist.github.com/xuwei-k/7b1e25992d7b70d01d72

Genの生成部分なのかviewMで変換する部分なのかすらよくわかってないですが、どちらの実装でもIListとか当てはめるとStackoverflowするので誰か助けてください。

あと、(流石に論文になってるんだから、間違ってないと信じたいけど)このFree MonadPlusがlaw満たす証明みたいなものってどこかにないんですかね？
そして、このFree MonadPlus最初に考えついたのは誰なんでしょうか？(この論文？別の論文？)

さて、Scalaが(Stackoverflowするという点において)残念なのはあれとして、このFree MonadPlusは、ekmett/freeに入ったりしないんでしょうか？(実は既に入ってる？)
実は存在を知ってて、あえて入れてない理由とかあるんでしょうか？
もしくは、このFree MonadPlusを実装してるekmett/free以外のHaskellライブラリが既に存在したりするんでしょうか？


色々疑問は尽きないですが、あと、肝心の論文の内容読めてないので、この後読みます。