重新实现 Map.fromListWith 函数

Question

我一直在尝试在 Haskell 中重新实现 Map.fromListWith 函数，但我运行遇到了一个我不明白的错误。

这是我的实现：

fromListWith_ :: (a -> a -> a) -> [(k, a)] -> Map.Map k a
fromListWith_ fn = foldl foldfn Map.empty
  where
    foldfn :: (Map.Map k a) -> (k, a) -> Map.Map k a
    foldfn m (key, val) = Map.insertWith fn key val m

这是我的错误：

Lecture8.hs:33:49: error:
    • Couldn't match expected type 'a' with actual type 'a1'
      'a1' is a rigid type variable bound by
        the type signature for:
          foldfn :: forall k1 a1. Map.Map k1 a1 -> (k1, a1) -> Map.Map k1 a1
        at src/Lecture8.hs:32:15
      'a' is a rigid type variable bound by
        the type signature for:
          fromListWith_ :: forall a k.
                           (a -> a -> a) -> [(k, a)] -> Map.Map k a
        at src/Lecture8.hs:29:18
    • In the third argument of 'Map.insertWith', namely 'val'
      In the expression: Map.insertWith fn key val m
      In an equation for 'foldfn':
          foldfn m (key, val) = Map.insertWith fn key val m
    • Relevant bindings include
        val :: a1 (bound at src/Lecture8.hs:33:20)
        m :: Map.Map k1 a1 (bound at src/Lecture8.hs:33:12)
        foldfn :: Map.Map k1 a1 -> (k1, a1) -> Map.Map k1 a1
          (bound at src/Lecture8.hs:33:5)
        fn :: a -> a -> a (bound at src/Lecture8.hs:30:15)
        fromListWith_ :: (a -> a -> a) -> [(k, a)] -> Map.Map k a
          (bound at src/Lecture8.hs:30:1)

我尝试从 foldfn 中删除类型注释，这会产生不同的错误：

Lecture8.hs:32:26: error:
    • No instance for (Ord k) arising from a use of ‘foldfn’
      Possible fix:
        add (Ord k) to the context of
          the type signature for:
            fromListWith_ :: (a -> a -> a) -> [(k, a)] -> Map.Map k a
    • In the first argument of ‘foldl’, namely ‘foldfn’
      In the expression: foldl foldfn Map.empty
      In an equation for ‘fromListWith_’:
          fromListWith_ fn
            = foldl foldfn Map.empty
            where
                foldfn m (key, val) = Map.insertWith fn key val m

非常感谢任何帮助。

Answer 1

我认为您的实现一切正常 - 您需要 ScopedTypeVariables 来处理内部函数的类型：

{-# LANGUAGE ScopedTypeVariables #-}

fromListWith_ :: forall a k. Ord k => (a -> a -> a) -> [(k, a)] -> Map.Map k a
fromListWith_ fn = foldl foldfn Map.empty
  where
    foldfn :: Map.Map k a -> (k, a) -> Map.Map k a
    foldfn m (key, val) = Map.insertWith fn key val m

没有那些 scoped 变量 foldfn :: (Map.Map k a) -> (k, a) -> Map.Map k a 中的 a 被假定为不同的类型变量（有点像 shadowing) - 当然与 k 相同。

注意： 要完成这项工作，您还需要明确的 forall！

如果您不喜欢这个，请删除签名：

fromListWith_ :: Ord k => (a -> a -> a) -> [(k, a)] -> Map.Map k a
fromListWith_ fn = foldl foldfn Map.empty
  where
    foldfn m (key, val) = Map.insertWith fn key val m

PS: 你也缺少 Ord k 约束。

insertWith 包含此约束，因此您需要传播它。

重新实现 Map.fromListWith 函数

Reimplementing Map.fromListWith function

haskell

functional-programming

higher-order-functions