正在重新实现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

---

如果没有这些范围的变量，foldfn :: (Map.Map k a) -> (k, a) -> Map.Map k a中的a被假设为不同类型的变量(有点像阴影(——当然与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包括这个约束，所以你需要传播它