☰

自由モナドは常に存在するのか？質問する

tag-icon • tag-icon haskell category-theory free-monad
自由モナドは常に存在するのか？質問する

圏論から、すべての自己関数子がセット自由モナドを認める。標準的な反例はべき集合関数である。

しかし、Haskell は任意の関数を自由モナドに変換できます。

data Free f a = Pure a | Free (f (Free f a))
instance Functor f => Monad (Free f) where
  return = Pure
  Pure a >>= f = f a
  Free m >>= f = Free ((>>= f) <$> m)

この構成がHaskellのどの関数でも機能するが、セット?

ベストアンサー1

この答えは明らかになった間違っている誰かが結論を出すまで、コメント欄で貴重な議論を残すためにここに残しておきます。正しい答え。

のべき乗集合を考えますSet。関数 がある場合f : S -> T、f' : PS S -> PS Tによってを形成できますf' X = f [X]。これは素晴らしい共変関数です (私はそう思います)。また、 も形成できます。これはf'' X = f^(-1) [X]素晴らしい反変関数です (私はそう思います)。

Haskell の「べき集合」を見てみましょう。

newtype PS t = PS (t -> Bool)

これはない、Functorただし のみContravariant:

instance Contravariant PS where
  contramap f (PS g) = PS (g . f)

tこれは、が負の位置にあるためわかります。 とは異なりSet、べき集合を構成する特性関数の「要素」を取得できないため、共変関数は使用できません。

したがって、Haskell がすべての共変関数に対して自由モナドを認める理由は、問題を引き起こす共変関数を除外するためだと推測しますSet。

おすすめ記事