ekmett/free の Cofree のインスタンスがバグってる？

[Kenji Yoshida]

こんにちは。

以前もekmett/semigroupoidsのバグに関して同じような投稿しましたが、またバグっぽいものを見つけたけど自信がないので、一旦ここで質問させてください。

端的にいうと、このCofreeのApplicativeのインスタンスが

https://github.com/ekmett/free/blob/b229616f6/src/Control/Comonad/Cofree.hs#L165-L169

がバグっている(Applicative則を満たさない)と思うのですが、どうでしょうか？

バグっているというのは最新のmasterの話で、現状の最新の安定versionの4.2(9ヶ月くらい前にでた)では正しかったと思うのです。

これ

https://github.com/ekmett/free/issues/36

で、「MonadとApplicativeのpureとreturnが異なる」ということで、今まで

instance Applicative f => Applicative (Cofree f) where

という制約だったのが

instance Alternative f => Applicative (Cofree f) where

という制約に変わってますが、これでバグを入れたと思うのです。
この変更自体もバグ修正ですが、これで逆にCofreeのApplicativeのインスタンスがバグった(?)ということは、
そもそも最初に入れたMonadのインスタンスの定義自体がおかしい(もとのApplicativeのほうにあわせて、Monadのインスタンスの方を修正するべきだった？)
か、そもそもCofreeはMonadになれない？
と思うのです。




ちなみに、バグを見つけた経緯とバグの根拠としては、ekmett/freeのversion4.2の時点のCofreeのインスタンスをScalazに翻訳したら

https://github.com/xuwei-k/scalaz/compare/scalaz:6e37bc0...xuwei-k:31cf150

テストが通って、それを今度はekmett/freeの最新のmasterにあわせて、Applicativeの定義変えてMonadを追加したら

https://github.com/xuwei-k/scalaz/compare/scalaz:6e37bc0...xuwei-k:54058a4
https://travis-ci.org/xuwei-k/scalaz/jobs/15506919#L3065

Applicativeのlawのテストが失敗するようになりました。




なにか自分が勘違いしている可能性もありますが
(もしくは、そもそもちゃんとekmett/freeをScalaに翻訳できていない?)
どんな細かいことでもいいので、助言お願いします。

[Kenji Yoshida]

Monadにすることは可能そうだし、Monadのインスタンス自体はMonad則満たすようので

「Monadにはなるし、Monadを整合性を保つためにApplicativeのインスタンスは修正するべきだったけど、修正方法が間違ってた」

でしょうか。

2013年12月16日 14:00 Kenji Yoshida <6b656...@gmail.com>:

--
このメールは Google グループのグループ「haskell-jp」の登録者に送られています。
このトピックの登録を解除するには、https://groups.google.com/d/topic/haskell-jp/TEn0_-RbKUs/unsubscribe にアクセスします。このグループから退会し、グループのすべてのトピックの登録を解除するには、haskell-jp+...@googlegroups.com にメールを送信します。
その他のオプションについては、https://groups.google.com/groups/opt_out にアクセスしてください。

[Kenji Yoshida]

再び自己レスすいません。ApplicativeとMonadは整合性ありますね

整合性ないのはApplyでした

https://github.com/ekmett/free/blob/b229616f6/src/Control/Comonad/Cofree.hs#L149-L155

[nobu_t...@nifty.com]

昨日から Cofree 勉強し始めました。
わからないことが多いので逆に質問ですが。

Apply f でなくて Applicative f だと Apply (Cofree f) は言えそうですか。

Control.Functor.Apply に載っている Applicative でない Apply の例
（例えば Compose とか）でも成り立ちそうですか。
（つまり反例を見つけるには Control.Functor.Apply に載っている以外の
Functor をさがしてこないといけなそうか）

解答でなくて質問で申し訳ないです。
---

[Kenji Yoshida]

返信ありがとうございます。

自分の説明が足りなかったり、そもそも以前書いたときの自分の理解も足りなくて混乱を招く説明してたので、ちょっと話が食い違ってる？感じがします。
質問の回答になるかわかりませんが、最初に投稿した後に色々考えて理解も進んだので、もう一度現状の自分の考えを説明してみます。



まず、現在のApply自体は、おそらくApply則そのものは満たします。(Apply則は以下のもの)

https://github.com/ekmett/semigroupoids/blob/v4.0/src/Data/Functor/Bind.hs#L95

ただし、それが(現在のmasterにある)ApplicativeやMonadとの整合性がない、というのがポイントです。
(ここで、CofreeをApplyにするために、どのような制約が必要か？はあまり重要な問題ではありません)


現在のCofreeのApplyは

instance Apply f => Apply (Cofree f) where
(f :< fs) <.> (a :< as) = f a :< ((<.>) <$> fs <.> as)
(f :< fs) <. (_ :< as) = f :< ((<. ) <$> fs <.> as)
(_ :< fs) .> (a :< as) = a :< (( .>) <$> fs <.> as)

となってますが、整合性保つためには、単にApplicativeの定義とほぼ同じように以下のようにするべきでは？
という考えになりました

instance Alternative f => Apply (Cofree f) where
(<.>) = ap

https://github.com/ekmett/free/blob/b229616f69/src/Control/Comonad/Cofree.hs#L149-L155


また、じゃあ最初のころ(v3.2以前)に存在していたApplicativeやApplyのインスタンスはなんだったのか？
間違いだったのか？というとそうでもなくて
https://github.com/ekmett/free/blob/v3.2/src/Control/Comonad/Cofree.hs#L127-L141

「CofreeをApplyやApplicativeにする方法は2種類存在する」

のだという考えに至りました。
(おそらく、ListがZipListとして別の方法でApplicativeのインスタンスにするのが可能なのにちょうど対応する)


なので、v3.2の頃の定義も正しくて、本当は新しくCofreeのnewtypeを定義して、その定義を残しても良かったのではないかと思います。


結局歴史的には

1. ApplyやApplicativeのインスタンスが定義された(この時点ではMonadのインスタンスは無いし、Functor含めそれらに整合性がある)
2. Monadのインスタンスが追加された
3. 追加したMonadのインスタンスと、最初に存在していたApplicativeのインスタンスに整合性がないことがわかった
4. Applicativeの古い定義は消されて、Monadのインスタンスと整合性を保つために定義が変わった(古い定義はnewtypeにして残すべきだったかもしれないが、Monadと合わせるという意味でのこの修正自体は正しい)
5. Applicativeの修正の際にApplyも同時に修正するべきだった(？)が、修正漏れに自分が気づいた(イマココ

ということだと思います。


issue欄にコメントしたら、「そうだね、多分間違ってるね」的な返信がekmettからきたけど、

https://github.com/ekmett/free/issues/36#issuecomment-30728047

まだ、コードの修正はされてません。







2013年12月18日 13:55 <nobu_t...@nifty.com>: