理解组合函子类型的操作

Question

理解组合函子类型的操作

11

根据多个来源，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，但即使在那里，我也很难“看到”计算fmap (fmap f) x

有人能够提供一个清晰且完整的工作示例吗？对于Maybe的Tree进行fmapping时要注意Empty和Node吗？

先谢谢。

- Marco Faustinelli

2个回答

4

x的类型是f (g a)，例如，x可以是一组整数树的列表：[Tree Int]（也可以写成[] (Tree Int)，以使其与f (g x)更加匹配）。

举个例子，考虑函数succ :: Int -> Int，它将一个整数加1。那么，函数fmap succ :: Tree Int -> Tree Int会将树中的每个整数都增加1。此外，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)

- chi

这是我正在输入的内容： *Main > let x1 = [Node 1 Empty Empty] *Main > let x2 = x1 fmap (fmap succ) 错误！我做错了什么？现在我尝试使用Maybe... - Marco Faustinelli

仍然无法使其工作：

Main> let y1 = Node（Just 1）Empty Empty
Main> 让 y2 = y1 fmap（fmap succ）ERROR！

- Marco Faustinelli

这就是为什么我明确要求提供“清晰完整的工作示例”。谢谢！ - Marco Faustinelli

我在fmappings前面的x1/y1处犯了一个大错误。但我知道这里肯定有一些技巧。这次是-XDeriveFunctor。 - Marco Faustinelli

1

@Muzietto 如果你手动定义一个函子实例，就可以避免使用-XDeriveFunctor。然而，由于GHC现在可以自动派生它，所以只需让它自动完成会更方便。 - chi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- András Kovács · Accepted Answer

在最后一个定义中，x的类型是什么？

在讨论此问题之前，可以先问问 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操作。由于我们有x :: f (g a)，我们猜想应该对x进行fmap操作以获得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)

完成了。

总结一下这个技巧：

首先在你不知道如何进行的地方开一个洞。在这里，我们是在整个右侧放置了一个洞，但通常情况下，您对实现的大部分部分都有很好的想法，并且需要在特定的问题子表达式中放置洞。
通过查看类型，尝试缩小可能导致目标的实现范围以及不能导致目标的实现范围。填写新表达式并重新定位洞。在证明助手的术语中，这称为“细化”。
重复步骤2，直到您获得目标，此时您完成了，或者当前目标似乎不可能，在这种情况下回溯到您最后做出的非显然选择，然后尝试另一种细化。

以上技巧有时被戏称为“类型俄罗斯方块”。可能的缺点是，您可以通过玩“俄罗斯方块”来实现复杂的代码，而实际上不理解自己在做什么。有时候会陷入游戏中无法自拔的状态，那么您就必须开始真正思考这个问题。但最终，它可以让您理解本来可能难以理解的代码。

我个人一直都在经常使用TypedHoles，而且基本上成为了一种反射动作。我已经如此依赖它，以至于有一次不得不回到GHC 7.6时感到非常不舒服（但幸运的是，甚至在那里，您也可以模拟洞口）。