正在尝试在幻影类型上实现Functor

Question

给定以下代数数据类型：

data Foo = Bar Int | Baz Bool deriving Show

我试图实现一个Functor实例。

instance Functor Foo where
    fmap f (Bar x) = Bar (f x)
    fmap f (Baz x) = Baz (f x)

但我得到了这个编译时错误：

ghci> :l explore/FunctorExplore.hs 
[1 of 1] Compiling Main             ( explore/FunctorExplore.hs, interpreted )
explore/FunctorExplore.hs:3:18:
    The first argument of ‘Functor’ should have kind ‘* -> *’,
      but ‘Foo’ has kind ‘*’
    In the instance declaration for ‘Functor Foo’
Failed, modules loaded: none.

因此，我添加了一个a，试图满足编译器的要求：

data Foo a = Bar Int | Baz Bool deriving Show

但后来我得到了两个错误，据我所知，这基本上意味着(a -> b)函数不能应用于Int或Bool。a是一个泛型类型，而其他两个是特定类型。

ghci> :l explore/FunctorExplore.hs 
[1 of 1] Compiling Main             ( explore/FunctorExplore.hs, interpreted )
explore/FunctorExplore.hs:4:31:
    Couldn't match expected type ‘Int’ with actual type ‘b’
      ‘b’ is a rigid type variable bound by
          the type signature for fmap :: (a -> b) -> Foo a -> Foo b
          at explore/FunctorExplore.hs:4:9
    Relevant bindings include
      f :: a -> b (bound at explore/FunctorExplore.hs:4:14)
      fmap :: (a -> b) -> Foo a -> Foo b
        (bound at explore/FunctorExplore.hs:4:9)
    In the first argument of ‘Bar’, namely ‘(f x)’
    In the expression: Bar (f x)
explore/FunctorExplore.hs:4:33:
    Couldn't match expected type ‘a’ with actual type ‘Int’
      ‘a’ is a rigid type variable bound by
          the type signature for fmap :: (a -> b) -> Foo a -> Foo b
          at explore/FunctorExplore.hs:4:9
    Relevant bindings include
      f :: a -> b (bound at explore/FunctorExplore.hs:4:14)
      fmap :: (a -> b) -> Foo a -> Foo b
        (bound at explore/FunctorExplore.hs:4:9)
    In the first argument of ‘f’, namely ‘x’
    In the first argument of ‘Bar’, namely ‘(f x)’
Failed, modules loaded: none.

在这种情况下，我似乎无法创建Functor。我的问题还有更多的问题吗，即我缺少什么？

Answer 1

函数式编程中的一项关键技能是，在给定的情况下，掌握不做任何事情的正确方法。例如，当需要[[]]表示"一个平凡的解决方案"时，将[]表示"没有解决方案"作为递归搜索的基本情况会出现经典错误。因此，幻影类型的Functor实例，即常数函子，作为更大模式的明显平凡的基本情况也是有用的。

我可以展示用于构建类似容器的结构的通用工具包，如下所示：

newtype K a x = K a deriving Functor             -- K for konstant
{- fmap _ (K a) = K a -}
newtype I x = I x deriving Functor               -- I for identity
{- fmap k (I x) = I (k x) -}
newtype P f g x = P (f x, g x) deriving Functor  -- P for product
{- will give (Functor f, Functor g) => Functor (P f g), such that
   fmap k (P (fx, gx)) = P (fmap k fx, fmap k gx) -}
newtype S f g x = S (Either (f x) (g x))         -- S for sum
instance (Functor f, Functor g) => Functor (S f g) where
  fmap k (S (Left  fx))  = S (Left  (fmap k fx))
  fmap k (S (Right gx))  = S (Right (fmap k gx))

现在，任何递归数据结构都可以表示为顶部节点，它充当子结构的容器。

data Data f = Node (f (Data f))

例如，如果我想制作叶子上有数字的二叉树，我可以写入

type Tree = S (K Int) (P I I)

以指示树的节点结构是具有CCD_ 11且没有子树的叶或者具有一对子树的叉。我需要K来指出递归子结构的不存在。则树的类型为Data Tree。

对于这些事情，通常的递归方案是

fold :: Functor f => (f t -> t) -> Data f -> t
fold k (Node fd) = k (fmap (fold k) fd)

我们不需要做任何工作来实例化树，因为Tree已经是Functor了，因为它是从函数组件构建的。K Int的微不足道的fmap相当于说递归在到达一个叶时停止。

当然，当您通过模式匹配编写普通程序时，这些"编码"的数据类型会使您更难看到自己在做什么。这就是PatternSynonyms分机拯救你的地方。你可以说

pattern Leaf i    = Node (S (Left (K i)))
pattern Fork l r  = Node (S (Right (P (I l, I r))))

以恢复通常的接口。我建议去掉外面的Node，以适合fold带Node的方式。

pattern Leaf i = S (Left (K i))
pattern Fork l r = S (Right (P (I l, I r)))
add :: Data Tree -> Int
add = fold $  t -> case t of
  Leaf i   -> i
  Fork x y -> x + y

无论何时，只要您可以为K、I、P和S开发大量数据类型，我都几乎没有触及到您可以将其扩展到这些数据类型的通用功能的表面。K病例总是微不足道的，但它们必须存在。

类似的注意事项适用于Void数据类型（在Data.Void中）。我们究竟为什么要费力地引入一种没有值得一提的元素的数据类型？为更大方案的不可能的情况建模。

Answer 2

由于a是幻影类型，因此根本无法应用f，但可以执行以下操作：

instance Functor Foo where
    fmap _ (Bar x) = Bar x
    fmap _ (Baz x) = Baz x