地图数据结构实现

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 实际上并没有做太多事情（除了将数据重新打包到 new 元组中）。输出元组的类型应该是 (a, b) 而不是 (a, a1)（a1 是 Map 中 values 的原始类型）。

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

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

或者更简洁的方式：

instance Functor (Map a) where
  fmap f (Map xs) = Map <b>(fmap (fmap f) xs)</b>

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

地图数据结构实现

Map data structure implementation

haskell

functor