地图数据结构实现

Question

这个Functor实例有什么问题？

data Map k v = Map [(k, v)] deriving (Show, Eq)
instance Functor (Map a) where
  fmap _ (Map []) = Map []
  fmap f (Map xs) = Map xs'
    where xs' = map ((k, v) -> (f k, v)) xs

Answer 1

如果我们编译它，我们得到错误：

<interactive>:6:21: error:
    • Couldn't match type ‘a1’ with ‘b’
      ‘a1’ is a rigid type variable bound by
        the type signature for:
          fmap :: forall a1 b. (a1 -> b) -> Map a a1 -> Map a b
        at <interactive>:5:3
      ‘b’ is a rigid type variable bound by
        the type signature for:
          fmap :: forall a1 b. (a1 -> b) -> Map a a1 -> Map a b
        at <interactive>:5:3
      Expected type: Map a b
        Actual type: Map a a1
    • In the expression: Map xs'
      In an equation for ‘fmap’:
          fmap f (Map xs)
            = Map xs'
            where
                xs' = map ( (k, v) -> (k, v)) xs
      In the instance declaration for ‘Functor (Map a)’
    • Relevant bindings include
        xs' :: [(a, a1)] (bound at <interactive>:7:11)
        xs :: [(a, a1)] (bound at <interactive>:6:15)
        f :: a1 -> b (bound at <interactive>:6:8)
        fmap :: (a1 -> b) -> Map a a1 -> Map a b
          (bound at <interactive>:5:3)

该错误实际上是一个很好的起点：它说您的fmap应该有签名：

fmap :: forall a1 b. (a1 -> b) -> Map a a1 -> Map a b

但显然您的输出类型是 Map a a1 ，因此您没有满足这些合同。如果我们进一步调查，我们会发现map ((k, v) -> (k, v)) xs实际上并没有做太多事情(除了在新元组中重新打包数据(。输出元组的类型应该有 (a, b) 而不是 (a, a1)(a1是Map中值的原始类型(。

因此，我们应该对值应用f，例如：

instance Functor (Map a) where
  fmap _ (Map []) = Map []
  fmap f (Map xs) = Map xs'
    where xs' = map ((k, v) -> (k, f v)) xs

或者以更干净的方式：

instance Functor (Map a) where
  fmap f (Map xs) = Map (fmap (fmap f) xs)

请注意，您不需要在此处实现两个单独的情况(一个用于空列表，一个用于非空列表(，因为空列表上的map(或fmap(是空列表。