Haskell中函数作为类型：字典插入函数实现困惑

我明白你在把函数当作字典类型时的困惑——这种用a -> Maybe b模拟键值映射的思路和传统的哈希表/数组字典完全不同，本质是靠函数的行为来定义键值对应关系。咱们一步步解决插入函数的问题：

1. 先明确函数式字典的定义 #

首先我们把字典类型定义为一个函数：

type Dict a b = a -> Maybe b

这个类型的含义很直接：一个Dict a b就是接收一个键a，返回对应值的Maybe b（Just b表示存在该键，Nothing表示不存在）。比如空字典就是不管传什么键都返回Nothing：

empty :: Dict a b
empty = const Nothing

2. 为什么你的插入方案会丢弃原字典？ #

你之前的错误大概率是直接返回了一个只处理新键的函数，完全忽略了原字典的逻辑。比如这种错误写法：

-- 错误：覆盖所有键的查询结果，原字典被丢弃
badInsert :: a -> b -> Dict a b -> Dict a b
badInsert k v _ = \_ -> Just v

这个函数返回的新字典，不管查询什么键都会返回Just v，自然丢失了原字典里的所有条目。

3. 正确的插入函数实现 #

正确的思路是：新字典需要优先处理插入的键，其他键委托给原字典查询。因为要比较键是否相等，所以需要给键的类型加Eq a约束：

insert :: Eq a => a -> b -> Dict a b -> Dict a b
insert k v existingDict = \queryKey ->
  if queryKey == k
    then Just v  -- 查到插入的键，返回新值
    else existingDict queryKey  -- 其他键，用原字典的结果

4. 验证一下效果 #

我们用实际例子测试：

1. 先创建空字典，插入键"apple"和值5：

   dict1 :: Dict String Int
   dict1 = insert "apple" 5 empty
   

   此时dict1 "apple"返回Just 5，dict1 "banana"返回Nothing，符合预期。

2. 再给dict1插入"banana"和值10：

   dict2 :: Dict String Int
   dict2 = insert "banana" 10 dict1
   

   此时dict2 "apple"返回Just 5，dict2 "banana"返回Just 10，完美保留了原字典的条目。

额外小知识点 #

这种函数式字典的查询逻辑其实就是它本身——因为Dict a b就是a -> Maybe b，所以查询函数可以直接写成：

lookup :: a -> Dict a b -> Maybe b
lookup key dict = dict key

这种实现方式虽然没有哈希表的高效查询性能，但胜在完全符合纯函数的理念：所有操作都返回新的函数，没有任何副作用，非常适合函数式编程的场景。

内容的提问来源于stack exchange，提问作者user7235699