以下类型的 Functor 实例是什么：newtype F2 x a = F2 ((a -> x) -> a)

Question

所以我想为上述类型编写 fmap 函数，但我被困在这里：

instance Functor (F2 x) where
 fmap :: (a -> b) -> (F2 x a) -> (F2 x b)
 fmap f (F2 g) = F2 ( f _ )

Answer 1

这里一个好的策略是遵循类型。如果我们使用 typed holes:

编写不完整的定义，GHC 可以一路帮助我们

newtype F2 x a = F2 ((a -> x) -> a)

instance Functor (F2 x) where
    fmap f (F2 g) = _

如果我们尝试编译它，GHC 会返回报告：

Diatonic.hs:275:21: error:
    • Found hole: _ :: F2 x b
      Where: ‘b’ is a rigid type variable bound by
               the type signature for:
                 fmap :: forall a b. (a -> b) -> F2 x a -> F2 x b
               at Diatonic.hs:275:5-8
             ‘x’ is a rigid type variable bound by
               the instance declaration
               at Diatonic.hs:274:10-23
    • In the expression: _
      In an equation for ‘fmap’: fmap f (F2 g) = _
      In the instance declaration for ‘Functor (F2 x)’
    • Relevant bindings include
        g :: (a -> x) -> a (bound at Diatonic.hs:275:16)
        f :: a -> b (bound at Diatonic.hs:275:10)
        fmap :: (a -> b) -> F2 x a -> F2 x b (bound at Diatonic.hs:275:5)
    |
275 |     fmap f (F2 g) = _
    |

这意味着我们必须用 F2 x b 值来填充这个洞。我们创建一个的唯一方法是使用构造函数（对于以下步骤，我将省略不变的样板）：

fmap f (F2 g) = F2 _

• Found hole: _ :: (b -> x) -> b

所以我们需要一个接受 b -> x 的函数。我们可以设置一个。让我们调用它的参数k，看看我们是否可以完成它的主体：

fmap f (F2 g) = F2 (\k -> _)

• Found hole: _ :: b

唯一能产生b的是f :: a -> b:

fmap f (F2 g) = F2 (\k -> f _)

• Found hole: _ :: a

唯一能产生a的是g :: (a -> x) -> a:

fmap f (F2 g) = F2 (\k -> f (g _))

• Found hole: _ :: a -> x

我们应该提供一个 a -> x 函数，所以让我们加入另一个 lambda（有关可能的快捷方式，请参阅答案的最后部分）：

fmap f (F2 g) = F2 (\k -> f (g (\a -> _)))

• Found hole: _ :: x

唯一能产生x的是k :: b -> x

fmap f (F2 g) = F2 (\k -> f (g (\a -> k _)))

• Found hole: _ :: b

唯一能产生b的是f :: a -> b:

fmap f (F2 g) = F2 (\k -> f (g (\a -> k (f _))))

• Found hole: _ :: a

如果我们尝试使用 g 来创建一个 a 值，就像我们在几个步骤之前所做的那样，我们将陷入恶性循环。但是，这次我们不必这样做，因为 lambda 的 a 参数在范围内：

fmap f (F2 g) = F2 (\k -> f (g (\a -> k (f a))))

我们完成了。

（值得一提的是，你的F2是由transformers、where it is known as Select提供的。）

如果我们写成\a -> k (f a) pointfree:

，这个定义可以说看起来更简洁一些

instance Functor (F2 x) where
    fmap f (F2 g) = F2 (\k -> f (g (k . f)))

我们可能会直接从 a -> x 的漏洞跳到这里，因为我们注意到我们唯一可行的选择是组合 f :: a -> b 和 k :: b -> x。

Answer 2

您可以让 GHC 为您完成繁重的工作：

GHCi, version 8.8.2: https://www.haskell.org/ghc/  :? for help
Prelude> :set -ddump-deriv -dsuppress-all -XDeriveFunctor
Prelude> newtype F2 x a = F2 ((a -> x) -> a) deriving(Functor)

==================== Derived instances ====================
Derived class instances:
  instance Functor (F2 x) where
    fmap f_a1bk (F2 a1_a1bl)
      = F2
          ((\ b4_a1bm b5_a1bn
              -> f_a1bk
                   (b4_a1bm
                      ((\ b2_a1bo b3_a1bp
                          -> (\ b1_a1bq -> b1_a1bq) (b2_a1bo (f_a1bk b3_a1bp)))
                         b5_a1bn)))
             a1_a1bl)
    (<$) z_a1br (F2 a1_a1bs)
      = F2
          ((\ b6_a1bt b7_a1bu
              -> (\ b5_a1bv -> z_a1br)
                   (b6_a1bt
                      ((\ b3_a1bw b4_a1bx
                          -> (\ b2_a1by -> b2_a1by)
                               (b3_a1bw ((\ b1_a1bz -> z_a1br) b4_a1bx)))
                         b7_a1bu)))
             a1_a1bs)


Derived type family instances:


Prelude>

重命名 GHC 的怪异名称并删除其过多的缩进，你最终会得到这样的结果：

instance Functor (F2 x) where
  fmap f (F2 a1) = F2 ((\b4 b5 -> f (b4 ((\b2 b3 -> (\b1 -> b1) (b2 (f b3))) b5))) a1)

现在我们可以做一些简化，让它更容易理解。让我们看看这个子表达式：

(\b2 b3 -> (\b1 -> b1) (b2 (f b3))) b5

(\b1 -> b1) 是恒等函数，我们可以通过 beta-reduce 去掉它：

(\b2 b3 -> b2 (f b3)) b5

现在我们可以再次进行 beta-reduce，这次 b5 for b2:

\b3 -> b5 (f b3)

这显然等同于 b5 . f。重新插入：

instance Functor (F2 x) where
  fmap f (F2 a1) = F2 ((\b4 b5 -> f (b4 (b5 . f))) a1)

另一个 beta 缩减：a1 for b4:

instance Functor (F2 x) where
  fmap f (F2 a1) = F2 (\b5 -> f (a1 (b5 . f)))

大功告成！不需要我们的努力。

以下类型的 Functor 实例是什么：newtype F2 x a = F2 ((a -> x) -> a)

What would be the Functor instance for the following type: newtype F2 x a = F2 ((a -> x) -> a)

haskell

functor