制作数据类型* - > *这不是一个Functor [英] Make Data Type of Kind * -> * That's Not a Functor

问题描述

Brent Yorgey的 Typeclassopedia 给出以下练习：

给出一个类型的例子 * - > * 不能成为
实体 Functor （不使用 undefined ）。

请告诉我什么不能成为 Functor b
$ b

另外，我会感激一个例子，但也许作为一个破坏者，以便你可以，请引导我到答案。


解决方案

让我们来讨论差异。

概念。考虑类型 A - >乙。我想让你想象的是，这种类型类似于有 B ，还有欠$ A 。事实上，如果您还清您的 A ，您会立即收到您的 B 。函数就像这样托管。

有和欠的概念可以扩展到其他类型。例如，最简单的容器

  newtype Box a = Box a 
  

的行为如下：如果你有一个 Box a ，那么你也有一个 A 。我们考虑类型 * - > * 和有它们的参数是（协变）函子，我们可以将它们实例化为 Functor

 实例Functor Box其中fmap f（Box a）= Box（fa）
  

如果我们考虑类型上的谓词类型，比如

  newtype Pred a = Pred（a  - > Bool）
  

在这种情况下，如果我们有一个 Pred a ，我们实际上欠了一个 a 。这出现在（ - >）箭头左侧的 a 。其中 Functor 的 fmap 是通过将函数传入容器并将其应用于所有我们拥有 我们的内在类型，我们不能对 Pred a 做同样的事情，因为我们没有have和 a

相反，我们会这样做

  class逆变换f其中
 contramap ::（a  - > b） - > （fb  - > fa）
  

现在 contramap 就像一个翻转 fmap ？它将允许我们将函数应用于我们在 Pred b 中拥有 b 的地方，以便收到 Pred a 。我们可以调用 contramap barter，因为它编码的思想是，如果您知道如何从<$获得 b s c $ c> a s，那么您可以将 b s的债务转换为 a


让我们看看它是如何工作的



  instance逆变换Pred 
 contramap f（Pred p）= Pred（\ a  - > p（fa））
  

我们在将它传递给谓词函数之前，先使用 f 来运行交易。很好！

现在我们有协变和逆变类型。从技术上讲，这些被称为协变和逆变函子。我也会立即说，几乎总是一个逆变函数也不是协变的。因此，这就回答了你的问题：存在一堆不能被实例化为 Functor 的逆变函子。 Pred 就是其中之一。

尽管如此，棘手的类型既是逆变函数也是协变函子。特别是，常量仿函数：

  data Z a = Z  - 幻影a！ 
 
实例Functor Z其中fmap _ Z = Z 
实例Contravariant Z其中contramap _ Z = Z 
  

事实上，你可以证明任何既是 Contravariant 和 Functor 有一个幻影参数。

  isPhantom ::（Functor f，Contravariant f）=> f a  - > f b  - 胁迫？！ 
 isPhantom = contramap（const（））。 fmap（const（）） - 不是真的... 
  

另一方面，一种类似于

   - 来自Data.Monoid 
 newtype Endo a = Endo（a  - > a）
  

在 Endo a 我们都欠并且收到 A 。这是否意味着我们没有债务？好吧，不，这意味着 Endo 既想要协变又要逆变，而 没有幻影参数。结果是： Endo 是不变的，并且既不能实例化 Functor 也不逆变。

Brent Yorgey's Typeclassopedia gives the following exercise:

Give an example of a type of kind * -> * which cannot be made an instance of Functor (without using undefined).

Please tell me what "cannot be made an instance of Functor" means.

Also, I'd appreciate an example, but perhaps as a spoiler so that you can, please, guide me to the answer.

解决方案

Let's talk about variances.

Here's the basic notion. Consider the type A -> B. What I want you to imagine is that such a type is similar to "having a B" and also "owing an A". In fact, if you pay back your A you immediately receive your B. Functions are kind of like escrow in that way.

The notion of "having" and "owing" can extend to other types. For instance, the simplest container

newtype Box a = Box a

behaves like this: if you "have" a Box a then you also "have" an a. We consider types which have kind * -> * and "have" their argument to be (covariant) functors and we can instantiate them to Functor

instance Functor Box where fmap f (Box a) = Box (f a)

What happens if we consider the type of predicates over a type, like

newtype Pred a = Pred (a -> Bool)

in this case, if we "have" a Pred a, we actually "owe" an a. This arises from the a being on the left side of the (->) arrow. Where fmap of Functor is defined by passing the function into the container and applying it to all the places where we "have" our inner type, we can't do the same for Pred a since we don't "have" and as.

Instead, we'll do this

class Contravariant f where
  contramap :: (a -> b) -> (f b -> f a)

Now that contramap is like a "flipped" fmap? It will allow us to apply the function to the places where we "own" a b in Pred b in order to receive a Pred a. We might call contramap "barter" because it encodes the idea that if you know how to get bs from as then you can turn a debt of bs into a debt of as.

Let's see how it works

instance Contravariant Pred where
  contramap f (Pred p) = Pred (\a -> p (f a))

we just run our trade using f prior to passing it on into the predicate function. Wonderful!

So now we have covariant and contravariant types. Technically, these are known as covariant and contravariant "functors". I'll also state immediately that almost always a contravariant functor is not also covariant. This, thus, answers your question: there exist a bunch of contravariant functors which are not able to be instantiated to Functor. Pred is one of them.

There are tricky types which are both contravariant and covariant functors, though. In particular, the constant functors:

data Z a = Z -- phantom a!

instance Functor       Z where fmap      _ Z = Z
instance Contravariant Z where contramap _ Z = Z

In fact, you can essentially prove that anything which is both Contravariant and Functor has a phantom parameter.

isPhantom :: (Functor f, Contravariant f) => f a -> f b   -- coerce?!
isPhantom = contramap (const ()) . fmap (const ())        -- not really...

On the other hand, what happens with a type like

-- from Data.Monoid
newtype Endo a = Endo (a -> a)

In Endo a we both owe and receive an a. Does that mean we're debt free? Well, no, it just means that Endo wants to be both covariant and contravariant and does not have a phantom parameter. The result: Endo is invariant and can instantiate neither Functor nor Contravariant.

这篇关于制作数据类型* - > *这不是一个Functor的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！