使数据类型为种类 * -> * 这不是函子

Question

Brent Yorgey的Typeclassopedia给出了以下练习：

举一个不能成为* -> *类型的示例 Functor实例（不使用undefined）。

请告诉我"不能成为Functor的实例"是什么意思。

另外，我希望有一个例子，但也许作为剧透，以便您可以引导我找到答案。

Answer 1

让我们谈谈方差。

这是基本概念。考虑类型 A -> B .我想让你想象的是，这种类型类似于"有B"，也类似于"欠A"。事实上，如果您偿还A，您会立即收到B。函数有点像托管的方式。

"

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

newtype Box a = Box a

行为是这样的：如果你"有"一个Box a那么你也"有"一个a.我们将具有种类* -> *并"具有"其参数的类型视为（协变）函子，我们可以将它们实例化为Functor

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

如果我们考虑谓词的类型而不是类型会发生什么，例如

newtype Pred a = Pred (a -> Bool)

在这种情况下，如果我们"有"Pred a，我们实际上"欠"了a。这是因为a位于(->)箭头的左侧。如果fmap Functor是通过将函数传递到容器中并将其应用于我们"拥有"内部类型的所有位置来定义的，我们不能对Pred a做同样的事情，因为我们没有"有"和a。

相反，我们会这样做

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

现在contramap就像一个"翻转"的fmap？它将使我们能够将该功能应用于我们在Pred b中"拥有"b的地方，以便 接收Pred a .我们可以称contramap为"易货贸易"，因为它编码了这样一种想法，即如果你知道如何从a中获取b，那么你就可以将b的债务变成a s的债务。

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

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

我们只是在将交易传递到谓词函数之前使用 f 运行我们的交易。美妙！

所以现在我们有协变和逆变类型。从技术上讲，这些被称为协变和逆变"函子"。我还要立即声明，几乎总是逆变函子不是协变的。因此，这回答了您的问题：存在一堆无法实例化为Functor的逆变函子。 Pred就是其中之一。

不过，有一些棘手的类型既是逆变函子又是协变函子。特别是常量函子：

data Z a = Z -- phantom a!
instance Functor       Z where fmap      _ Z = Z
instance Contravariant Z where contramap _ Z = Z

事实上，你基本上可以证明任何既Contravariant又Functor的东西都有一个幻影参数。

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

另一方面，像这样的类型会发生什么

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

Endo a我们既欠又收到a.这是否意味着我们没有债务？嗯，不，这只是意味着Endo既想协变又要逆变，并且没有幻像参数。结果：Endo是不变的，既不能实例化Functor也不能实例化Contravariant。

Answer 2

当

且仅当可以为它实现Functor类的守法实例时，* -> *类型的t可以成为Functor的实例。 所以这意味着你必须实现Functor类，你的fmap必须遵守Functor法则：

fmap id x == x
fmap f (fmap g x) == fmap (f . g) x

所以基本上，要解决这个问题，你必须说出你选择的某种类型，并证明没有合法的fmap实施。

让我们从一个非示例开始，以设定基调。 (->) :: * -> * -> *是函数类型构造函数，如 String -> Int :: * 等函数类型所示。 在 Haskell 中，您可以部分应用类型构造函数，因此您可以拥有类似 (->) r :: * -> * 的类型。 此类型是Functor：

instance Functor ((->) r) where
    fmap f g = f . g

直观地说，这里的Functor实例允许您g :: r -> a"之前"（可以这么说）将g应用于某些x :: r函数的返回值f :: a -> b。 例如，如果这是返回其参数长度的函数：

length :: [a] -> Int

。那么这是返回其参数长度两倍的函数：

twiceTheLength :: [a] -> Int
twiceTheLength = fmap (*2) length

有用的事实：Reader monad 只是(->)的一个newtype：

newtype Reader r a = Reader { runReader :: r -> a }
instance Functor (Reader r) where
    fmap f (Reader g) = Reader (f . g)
instance Applicative (Reader r) where
    pure a = Reader (const a)
    Reader f <*> Reader a = Reader $ r -> f r (a r)
instance Monad (Reader r) where
    return = pure
    Reader f >>= g = Reader $ r -> runReader g (f r) r

现在我们已经有了这个非示例，这里有一个不能做成Functor的类型：

type Redaer a r = Redaer { runRedaer :: r -> a } 
-- Not gonna work!
instance Functor (Redaer a) where
    fmap f (Redaer g) = ...

是的，

我所做的只是将名称向后拼写，更重要的是，翻转类型参数的顺序。 我会让你试着弄清楚为什么这个类型不能成为Functor的实例。