带折叠的地图查找功能

Question

我想使用折叠创建一个 "map lookup" 函数。

这是我的"map"（只是一个元组列表）：

phoneBook:: [([Char], [Char])]
phoneBook = [("bob", "00-21-55")
            ,("jack", "55-51-55")
            ,("joe", "10-61-25")
            ,("susy", "06-21-55")
            ,("clara", "50-31-95")
            ]

这就是我想要编写的函数类型：

lookUp :: (Eq k) => k -> [(k,v)] -> v
lookUp k = foldl1 (\acc (x,y) -> if k == y then y else acc)

但是，这不会编译，它会产生 "cannot construct infinite type" 错误。

你能给我解释一下为什么这是错误的吗？我该如何让它发挥作用？

请注意，我知道 Data.Map 及其导出的地图函数，我想这样做只是为了了解折叠的工作原理。

Answer 1

首先这是一个工作版本——我会在几分钟后回来解释：

lookUp :: (Eq k) => k -> [(k,v)] -> Maybe v
lookUp k = foldl (\ acc (k',v) -> if k == k' then Just v else acc) Nothing

您遇到的问题是：

对于 foldl1 你有类型 foldl1 :: (a -> a -> a) -> [a] -> a 所以你的元素和结果需要相同的类型 - 但在这里你想要值作为结果但是折叠 [=46= 的元组].
这就是我切换到更通用的 foldl 的原因（请注意，我对这是否是正确的选择不感兴趣 - 请参阅 foldl' vs foldl vs foldr)
这个函数永远不可能是完整的（如果键不在 dictionary/key-value-pair-list 中）所以我选择在结果类型中反映这一点，现在是 Maybe v - 当然这样就可以了很容易找到一个初始值：Nothing

如果您不喜欢 Maybe 部分，您也可以使用 error 代替：

lookUp :: (Eq k) => k -> [(k,v)] -> v
lookUp k = foldl (\ acc (k',v) -> if k == k' then v else acc) (error "key not found")

备注：

这不是最有效的实施方式，因为无论您是否找到了密钥，您都将浏览所有列表 - 请随意尝试想出一些可以做到的事情

提示: Haskell 是懒惰的 - 也许你可以通过过滤掉正确的 key/value-pairs 找到一些东西，取这个的安全头然后映射到值部分 ;) )

带折叠的地图查找功能

Map lookup function with fold

haskell

fold

备注：