不是Functor / Functor / Applicative / Monad的好例子？-Java 学习之路

188

在向某人解释什么是类型类X时，我很难找到正好是X的数据结构的好例子 .

所以，我请求示例：

一个不是Functor的类型构造函数 .
一个类型构造函数，它是一个Functor，但不是Applicative .
一个类型构造函数，它是一个Applicative，但不是Monad .
一个Monad的类型构造函数 .

我认为Monad到处都有很多例子，但Monad的一个很好的例子与之前的例子有一些关系可以完成图片 .

我查找了彼此相似的示例，仅在属于特定类型类的重要方面有所不同 .

如果有人能够设法在这个层次结构的某个地方隐藏一个Arrow的例子（在Applicative和Monad之间吗？），那也会很棒！

5 回答

65
A type constructor which is not a Functor:
```
newtype T a = T (a -> Int)
```
你可以用它来制作逆变函子，但不能用（协变）函子 . 尝试写 fmap ，你就会失败 . 请注意，逆变仿函数版本是相反的：
```
fmap      :: Functor f       => (a -> b) -> f a -> f b
contramap :: Contravariant f => (a -> b) -> f b -> f a
```
A type constructor which is a functor, but not Applicative:

我没有一个很好的例子 . 有 Const ，但理想情况下我认为没有 . 当您开始使用时，所有类型基本上都是数字，枚举，产品，总和或函数 . 你可以看到下面的pigworker，我不同意 Data.Void 是 Monoid ;
```
instance Monoid Data.Void where
    mempty = undefined
    mappend _ _ = undefined
    mconcat _ = undefined
```
由于 _|_ 在Haskell中是合法值，并且实际上是 Data.Void 的唯一合法值，因此符合Monoid规则 . 我不确定 unsafeCoerce 与它有什么关系，因为你的程序不再保证在你使用任何 unsafe 函数时不会违反Haskell语义 .

有关底部（link）或不安全函数（link）的文章，请参阅Haskell Wiki .

我想知道是否可以使用更丰富的类型系统创建这样的类型构造函数，例如具有各种扩展的Agda或Haskell .

A type constructor which is an Applicative, but not a Monad:
```
newtype T a = T {multidimensional array of a}
```
您可以使用以下内容制作应用程序：
```
mkarray [(+10), (+100), id] <*> mkarray [1, 2]
  == mkarray [[11, 101, 1], [12, 102, 2]]
```
但是如果你把它变成monad，你就会得到尺寸不匹配 . 我怀疑像这样的例子在实践中很少见 .

A type constructor which is a Monad:
```
[]
```
About Arrows:

询问箭头在这个层次结构上的位置就像问什么样的形状“红色” . 注意种类不匹配：
```
Functor :: * -> *
Applicative :: * -> *
Monad :: * -> *
```
但，
```
Arrow :: * -> * -> *
```
回复于 2024-04-20T07:16:19+08:00
20
我的风格可能会被我的手机弄得一团糟，但是现在这样 .
```
newtype Not x = Kill {kill :: x -> Void}
```
不能是一个Functor . 如果是，我们就有
```
kill (fmap (const ()) (Kill id)) () :: Void
```
月亮将由绿色奶酪制成 .

与此同时
```
newtype Dead x = Oops {oops :: Void}
```
是一个算符
```
instance Functor Dead where
  fmap f (Oops corpse) = Oops corpse
```
但不能适用，或者我们有
```
oops (pure ()) :: Void
```
和绿色将由月亮奶酪制成（实际上可以发生，但仅在晚上） .

（额外注意： Void ，如 Data.Void 中的数据类型为空 . 如果您尝试使用 undefined 来证明它's a Monoid, I'将使用 unsafeCoerce 来证明它不是 . ）

欢悦，
```
newtype Boo x = Boo {boo :: Bool}
```
在很多方面是适用的，例如Dijkstra会有的，
```
instance Applicative Boo where
  pure _ = Boo True
  Boo b1 <*> Boo b2 = Boo (b1 == b2)
```
但它不能是Monad . 要明白为什么不这样做，请注意返回必须经常 Boo True 或 Boo False ，因此
```
join . return == id
```
不可能举行 .

哦，是的，我差点忘了
```
newtype Thud x = The {only :: ()}
```
是Monad . 滚动你自己 .

飞机赶上......
回复于 2024-04-20T07:16:19+08:00
80
我相信其他答案错过了一些简单而常见的例子：

A type constructor which is a Functor but not an Applicative. 一个简单的例子是一对：
```
instance Functor ((,) r) where
    fmap f (x,y) = (x, f y)
```
但是如何在不对 r 施加额外限制的情况下如何定义其 Applicative 实例 . 特别是，没有办法如何为任意 r 定义 pure :: a -> (r, a) .

A type constructor which is an Applicative, but is not a Monad. 一个众所周知的例子是ZipList . （它是 newtype 包装列表并为它们提供不同的 Applicative 实例 . ）

fmap 以通常的方式定义 . 但 pure 和 <*> 被定义为
```
pure x                    = ZipList (repeat x)
ZipList fs <*> ZipList xs = ZipList (zipWith id fs xs)
```
所以 pure 通过重复给定值创建一个无限列表，并且 <*> 使用值列表压缩一系列函数 - 将第i个函数应用于第i个元素 . （ [] 上的标准 <*> 产生了将第i个函数应用于第j个元素的所有可能组合 . ）但是如何定义monad没有明智的方法（参见this post） .

How arrows fit into the functor/applicative/monad hierarchy? 见Sam Lindley，Philip Wadler，Jeremy Yallop撰写的Idioms are oblivious, arrows are meticulous, monads are promiscuous . MSFP 2008.（他们称之为applicative functors成语 . ）摘要：

我们重新审视了三个计算概念之间的联系：Moggi的monad，Hughes的箭头和McBride和Paterson的习语（也称为applicative functors） . 我们证明成语相当于满足类型同构A~> B = 1~>（A - > B）的箭头，并且monad相当于满足类型同构A~> B = A - >的箭头（1~ > B） . 此外，成语嵌入箭头和箭头嵌入monad .
回复于 2024-04-20T07:16:19+08:00
4

一个不是算子的类型构造函数的一个很好的例子是 Set ：你不能实现 fmap :: (a -> b) -> f a -> f b ，因为没有额外的约束 Ord b 你不能构造 f b .

回复于 2024-04-20T07:16:19+08:00
90
我想提出一个更系统的方法来回答这个问题，并举例说明不使用任何特殊技巧，如“底部”值或无限数据类型或类似的东西 .

类型构造函数何时无法具有类型类实例？

通常，有两个原因导致类型构造函数无法拥有某个类型类的实例：
- 无法从类型类实现所需方法的类型签名 .
- 可以实现类型签名但不能满足所需的法律 .
第一类的例子比第二类的例子容易，因为对于第一类，我们只需要检查是否可以实现具有给定类型签名的函数，而对于第二类，我们需要证明没有实现可能会满足法律 .

具体例子
- A type constructor that cannot have a functor instance 因为无法实现类型：
data F a = F (a -> Int)

这是一个反向函数，而不是一个仿函数，因为它在逆变位置使用类型参数 a . 使用类型签名 (a -> b) -> F a -> F b 实现函数是不可能的 .
- A type constructor that is not a lawful functor 即使可以实现 fmap 的类型签名：
data Q a = Q(a -> Int, a) fmap :: (a -> b) -> Q a -> Q b fmap f (Q(g, x)) = Q(\_ -> g x, f x) -- this fails the functor laws!

这个例子的好奇方面是我们可以实现正确类型的 fmap ，即使 F 不可能是一个仿函数，因为它在逆变位置使用 a . 因此，上面显示的 fmap 的这种实现具有误导性 - 即使它具有正确的类型签名（我相信这是该类型签名的唯一可能实现），但是不满足算子定律（这需要一些简单的计算来检查） .

事实上， F 只是一个变形金刚，它既不是算子也不是反向函数 .
- A lawful functor that is not applicative 因为 pure 的类型签名无法实现：取Writer monad (a, w) 并删除 w 应该是monoid的约束 . 因此，不可能在 a 中构造 (a, w) 类型的值 .
- A functor that is not applicative 因为无法实现 <*> 的类型签名： data F a = Either (Int -> a) (String -> a) .
- A functor that is not lawful applicative 即使可以实现类型类方法：
data P a = P ((a -> Int) -> Maybe a)

类型构造函数 P 是一个仿函数，因为它仅在协变位置使用 a .
```
instance Functor P where
   fmap :: (a -> b) -> P a -> P b
   fmap fab (P pa) = P (\q -> fmap fab $ pa (q . fab))
```
<*> 类型签名的唯一可能实现是始终返回 Nothing 的函数：
```
(<*>) :: P (a -> b) -> P a -> P b
 (P pfab) <*> (P pa) = \_ -> Nothing  -- fails the laws!
```
但是这种实现不满足应用函子的身份定律 .
- A functor that is Applicative but not a Monad 因为 bind 的类型签名无法实现 .
我不知道这样的例子！
- A functor that is Applicative but not a Monad 因为即使可以实现 bind 的类型签名也无法满足法律 .
这个例子产生了相当多的讨论，所以可以肯定地说，证明这个例子是正确的并不容易 . 但有几个人通过不同的方法独立验证了这一点 . 有关其他讨论，请参见Is data PoE a = Empty | Pair a a a monad? .
```
data B a = Maybe (a, a)
   deriving Functor

 instance Applicative B where
   pure x = Just (x, x)
   b1 <*> b2 = case (b1, b2) of
     (Just (x1, y1), Just (x2, y2)) -> Just((x1, x2), (y1, y2))
     _ -> Nothing
```
证明没有合法的 Monad 实例有点麻烦 . 非monadic行为的原因是，当函数 f :: a -> B b 可以为 a 的不同值返回 Nothing 或 Just 时，没有自然的方法来实现 bind .

或许更清楚的是考虑 Maybe (a, a, a) ，它也不是monad，并尝试实现 join . 人们会发现没有直观合理的方法来实施 join .
```
join :: Maybe (Maybe (a, a, a), Maybe (a, a, a), Maybe (a, a, a)) -> Maybe (a, a, a)
 join Nothing = Nothing
 join Just (Nothing, Just (x1,x2,x3), Just (y1,y2,y3)) = ???
 join Just (Just (x1,x2,x3), Nothing, Just (y1,y2,y3)) = ???
 -- etc.
```
在由 ??? 指示的情况下，似乎很清楚我们不能以任何合理和对称的方式从 a 类型的六个不同值中产生 Just (z1, z2, z3) . 我们当然可以选择这六个值中的一些任意子集 - 例如，总是采用第一个非空 Maybe - 但这不符合monad的定律 . 返回 Nothing 也不符合法律规定 .
- A tree-like data structure that is not a monad 即使它与 bind 具有关联性 - 但未通过身份法则 .
通常的树状单子（或“带有仿函数形状的树枝的树”）被定义为
```
data Tr f a = Leaf a | Branch (f (Tr f a))
```
这是一个免费的monad over the functor f . 数据的形状是树，其中每个分支点是子树的"functor-ful" . 标准二叉树将使用 type f a = (a, a) 获得 .

如果我们通过制作仿函数 f 形状的叶子来修改这个数据结构，我们得到了我所谓的"semimonad" - 它具有满足自然性和相关性定律的 bind ，但它的 pure 方法失败了一个身份定律 . "Semimonads are semigroups in the category of endofunctors, what's the problem?"这是类型类 Bind .

为简单起见，我定义了 join 方法而不是 bind ：
```
data Trs f a = Leaf (f a) | Branch (f (Trs f a))
 join :: Trs f (Trs f a) -> Trs f a
 join (Leaf ftrs) = Branch ftrs
 join (Branch ftrstrs) = Branch (fmap @f join ftrstrs)
```
分枝嫁接是标准的，但叶嫁接是非标准的并产生 Branch . 这不是关联法律的问题，而是打破了身份法之一 .

多项式类型何时具有monad实例？

函数 Maybe (a, a) 和 Maybe (a, a, a) 都不能给出合法的 Monad 实例，尽管它们显然是 Applicative .

这些仿函数没有任何技巧 - 没有 Void 或 bottom 任何地方，没有棘手的懒惰/严格，没有无限的结构，没有类型类约束 . Applicative 实例是完全标准的 . 函数 return 和 bind 可以为这些仿函数实现，但不符合monad的规律 . 换句话说，这些仿函数不是monad，因为缺少特定的结构（但不容易理解究竟缺少什么） . 作为一个例子，仿函数的一个小变化可以使它成为一个monad： data Maybe a = Nothing | Just a 是一个monad . 另一个类似的仿函数 data P12 a = Either a (a, a) 也是一个monad .

多项式monad的构造

一般来说，这里有一些结构可以产生多项式类型的合法_739529 . 在所有这些结构中， M 是一个monad：
- type M a = Either c (w, a) 其中 w 是任何幺半群
- type M a = m (Either c (w, a)) 其中 m 是任何monad而 w 是任何monoid
- type M a = (m1 a, m2 a) 其中 m1 和 m2 是任何monad
- type M a = Either a (m a) 其中 m 是任何monad
第一个建筑是 WriterT w (Either c) ，第二个建筑是 WriterT w (EitherT c m) . 第三种结构是monad的组件产品： pure @M 被定义为 pure @m1 和 pure @m2 的组件产品，而 join @M 是通过省略跨产品数据来定义的（例如 m1 (m1 a, m2 a) 通过省略第二部分而被映射到 m1 (m1 a) 元组）：
```
join :: (m1 (m1 a, m2 a), m2 (m1 a, m2 a)) -> (m1 a, m2 a)
 join (m1x, m2x) = (join @m1 (fmap fst m1x), join @m2 (fmap snd m2x))
```
第四种结构定义为
```
data M m a = Either a (m a)
 instance Monad m => Monad M m where
    pure x = Left x
    join :: Either (M m a) (m (M m a)) -> M m a
    join (Left mma) = mma
    join (Right me) = Right $ join @m $ fmap @m squash me where
      squash :: M m a -> m a
      squash (Left x) = pure @m x
      squash (Right ma) = ma
```
我已经检查过所有四种结构都会产生合法的单子 .

我猜想多项式monad没有其他结构 . 例如，仿函数 Maybe (Either (a, a) (a, a, a, a)) 不是通过任何这些结构获得的，因此不是monadic . 但是， Either (a, a) (a, a, a) 是monadic，因为它与三个monad a ， a 和 Maybe a 的乘积同构 . 此外， Either (a,a) (a,a,a,a) 是monadic，因为它与 a 和 Either a (a, a, a) 的乘积同构 .

上面显示的四个结构将允许我们获得任意数量的 a 的任意数量的产品的总和，例如 Either (Either (a, a) (a, a, a, a)) (a, a, a, a, a)) 等 . 所有这些类型构造函数都将具有（至少一个） Monad 实例 .

当然，还有待观察，这些单子可能存在哪些用例 . 另一个问题是通过结构1-4导出的 Monad 实例通常不是唯一的 . 例如，类型构造函数 type F a = Either a (a, a) 可以通过两种方式给出 Monad 实例：使用monad (a, a) 构造4，使用类型isomorphism Either a (a, a) = (a, Maybe a) 构造3 . 同样，找到这些实现的用例并不是很明显 .

问题仍然存在 - 给定任意多项式数据类型，如何识别它是否具有 Monad 实例 . 我不知道如何证明多项式monad没有其他结构 . 到目前为止，我认为没有任何理论可以回答这个问题 .
回复于 2024-04-20T07:16:19+08:00

不是Functor / Functor / Applicative / Monad的好例子？

5 回答

类型构造函数何时无法具有类型类实例？

具体例子

多项式类型何时具有monad实例？

多项式monad的构造

相关问题