带折叠的地图查找功能

Question

我想使用折叠创建一个"地图查找"功能.

这是我的"地图"(只是一个元组列表):

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)

但是,这不会编译,它会产生"无法构造无限类型"的错误.

你能解释一下为什么这是错的,我怎么能让它发挥作用？

请注意,我知道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所以你需要为你的元素和你的结果需要相同的类型 - 但是在这里你想要值作为结果但折叠键/值对的元组.
• 这就是为什么我转向更一般的foldl(注意我不感兴趣,如果这是正确的选择 - 见foldl'vs foldlvs foldr)
• 这个函数永远不会是完全的(如果键不在词典/键值对列表中)所以我选择在结果类型中反映这一点,现在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是懒惰的 - 也许你可以通过过滤掉正确的键/值对来找到一些东西,拿出这个的安全头然后maping到值部分;))