了解组合仿函数类型的操作

Question

根据多个消息来源，Haskell 组合仿函数的实现大致如下：

import Data.Functor.Compose

newtype Compose f g a = Compose { getCompose :: f (g a) }

instance (Functor f, Functor g) => Functor (Compose f g) where
    fmap f (Compose x) = Compose (fmap (fmap f) x)

我的问题是：最后一个定义中x的类型是什么？

我会说它是 f g a，但即使在那里我也很难 'see' 计算 fmap (fmap f) x

任何人都可以提供关于这一点的清晰完整的工作示例吗？将 Maybe 中的 Tree 同时关注 Empty 和 Node 怎么样？

提前致谢。

Answer 1

x的类型是f (g a)。例如，x 可能是一个整数树列表：[Tree Int]（也可以写成 [] (Tree Int) 以便更接近地匹配 f (g x)）。

例如，考虑函数 succ :: Int -> Int，它将一个整数加一。然后，函数 fmap succ :: Tree Int -> Tree Int 将递增树中的每个整数。此外，fmap (fmap succ) :: [Tree Int] -> [Tree Int] 会将前面的 fmap succ 应用于列表中的所有树，因此它将递增树列表中的每个整数。

如果您有 Tree (Maybe Int)，那么 fmap (fmap succ) 将递增此类树中的每个整数。 Nothing 形式的树中的值不会受到影响，而值 Just x 将增加 x。

示例：（GHCi 会话）

> :set -XDeriveFunctor
> data Tree a = Node a (Tree a) (Tree a) | Empty deriving (Show, Functor)
> let x1 = [Node 1 Empty Empty]
> fmap (fmap succ) x1
[Node 2 Empty Empty]
> let x2 = [Node 1 Empty Empty, Node 2 (Node 3 Empty Empty) Empty]
> fmap (fmap succ) x2
[Node 2 Empty Empty,Node 3 (Node 4 Empty Empty) Empty]
> let x3 = Just (Node 1 Empty Empty)
> fmap (fmap succ) x3
Just (Node 2 Empty Empty)

Answer 2

what is the type of x in the last definition?

在说这件事之前：你可以问GHC！ GHC 7.8 及更高版本支持 TypedHoles，这意味着如果您在表达式（而非模式）中放置下划线，然后点击加载或编译，您会收到一条消息，其中包含下划线的预期类型和变量类型本地范围。

newtype Compose f g a = Compose { getCompose :: f (g a) }

instance (Functor f, Functor g) => Functor (Compose f g) where
    fmap f (Compose x) = _

GHC 现在说，省略了一些部分：

Notes.hs:6:26: Found hole ‘_’ with type: Compose f g b …
    -- omitted type variable bindings --
    Relevant bindings include
      x :: f (g a)
        (bound at /home/kutta/home/Dropbox/src/haskell/Notes.hs:6:21)
      f :: a -> b
        (bound at /home/kutta/home/Dropbox/src/haskell/Notes.hs:6:10)
      fmap :: (a -> b) -> Compose f g a -> Compose f g b
        (bound at /home/kutta/home/Dropbox/src/haskell/Notes.hs:6:5)
    In the expression: _
    In an equation for ‘fmap’: fmap f (Compose x) = _
    In the instance declaration for ‘Functor (Compose f g)’

好了，x :: f (g a)。经过一些练习，TypedHoles 可以极大地帮助您理解复杂的多态代码。让我们尝试通过从头开始写出右侧来找出我们当前的代码。

我们已经看到该洞的类型为 Compose f g b。因此我们必须在右边有一个Compose _：

instance (Functor f, Functor g) => Functor (Compose f g) where
    fmap f (Compose x) = Compose _

新洞的类型为 f (g b)。现在我们应该看看上下文：

Relevant bindings include
  x :: f (g a)
    (bound at /home/kutta/home/Dropbox/src/haskell/Notes.hs:6:21)
  f :: a -> b
    (bound at /home/kutta/home/Dropbox/src/haskell/Notes.hs:6:10)
  fmap :: (a -> b) -> Compose f g a -> Compose f g b
    (bound at /home/kutta/home/Dropbox/src/haskell/Notes.hs:6:5)

目标是从上下文中的成分中得到 f (g b)。不幸的是，上面清单中的 fmap 指的是正在定义的函数，这有时很有用，但在这里没有用。我们最好知道 f 和 g 都是仿函数，因此它们可以被 fmap-ed 覆盖。由于我们有 x :: f (g a)，我们猜测我们应该 fmap 超过 x 以获得 f (g b):

fmap f (Compose x) = Compose (fmap _ x)

现在这个洞变成了g a -> g b。但是 g a -> g b 现在很容易，因为我们有 f :: a -> b 并且 g 是 Functor，所以我们还有 fmap :: (a -> b) -> g a -> g b，因此 fmap f :: g a -> g b .

fmap f (Compose x) = Compose (fmap (fmap f) x)

我们完成了。

总结技巧：

先在不知如何进行的地方打个洞。在这里，我们首先将孔放在整个右侧的位置，但通常您会对实现的大部分内容有一个很好的了解，并且您需要在特定的有问题的子表达式中使用孔。
通过查看类型，尝试缩小哪些实现可能导致目标而哪些不能。填充新表达式并重新定位孔。在证明助理术语中，这称为 "refining"。
重复第 2 步，直到您有目标，在这种情况下您已经完成，或者当前目标似乎不可能实现，在这种情况下回溯到您做出的最后一个不明显的选择，并且尝试另一种精炼方法。

上述技术有时被戏称为 "type tetris"。一个可能的缺点是您可以通过播放 "tetris" 来实现复杂的代码，而无需真正理解您在做什么。有时在走得太远之后，你会严重陷入游戏中，然后你必须开始真正思考问题。但最终它可以让您理解否则很难掌握的代码。

我个人一直使用 TypedHoles 并且基本上是一种条件反射。我已经变得非常依赖它，以至于在我不得不回到 GHC 7.6 的时候我感到很不舒服（但幸运的是你 can emulate holes 即使在那里）。

了解组合仿函数类型的操作

Understanding operations on composed functor types

haskell

functional-programming

functor