时间戳

首页 > 解决方案 > 以下类型的 Functor 实例是什么： newtype F2 xa = F2 ((a -> x) -> a)

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

问题描述

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

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

标签： haskellfunctor

解决方案

这里一个好的策略是遵循类型。如果我们用类型空洞编写不完整的定义，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

唯一可以产生 a 的b是f :: a -> b：

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

• Found hole: _ :: a

唯一可以产生 an 的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

唯一能产生a的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价值，我们就会陷入恶性循环。但是，这次我们不必这样做，因为alambda 的参数在范围内：

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

我们完成了。

（值得一提的是，你F2是由transformers提供的，它被称为Select。）

\a -> k (f a)如果我们写pointfree ，定义可以说看起来更整洁：

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

通过注意到我们a -> x唯一可行的选择是 composef :: a -> b和k :: b -> x.

推荐阅读