Map 必须包含所有可能的键？

提问于 2024-04-27T11:42:23+08:00

浏览次

4

Haskell有多个数据结构，如 Map key value ，在内部使用树或哈希映射 . 使用此数据结构时，可能在执行查找时，密钥将不存在 .

在我的用例中，可能的键集是有限的（技术上它们都在 Enum 和 Ord ）并且我只对存在所有键的映射感兴趣 .

如何创建一个类似于 Map 的数据结构，保证 Map 中存在所有键，即它可以具有非部分函数 lookup :: Map key value -> key -> value （可能有 key 类型的约束， Ord 或 Hashable 或其他任何东西）？有没有这样的东西？

换句话说：我想要一个只有在插入所有可能的密钥时才能查询的数据结构 . 我可以使用常规 Map 和 fromMaybe ，但我不想指定默认值 - 我想在类型级别保证永远不需要默认值 .

2 回答

7
您正在寻找的结构只是一个功能： Key -> Value . 您可以使用以下内容插入（或实际替换）值
```
insert :: (Key -> Value) -> Key -> Value -> (Key -> Value)
insert f k v k' = if k == k' then v else f k'
```
keys 和 values 函数实现起来很简单（您只需要将Key类型设置为 Enum ） . 编译器可以警告您函数是否是部分函数（最终，您使用的数据结构，您不能阻止某人插入 undefined 值） .
回复于 2024-04-27T11:42:23+08:00
9
你应该研究一种称为 memo(ization) tries 的技术 . 函数类型 A -> B 的备忘录是一种数据类型，它将该类型的函数表示为记录所有参数/结果组合的数据结构 . 您可以浏览一些链接：
但是长话短说，Haskell中的备忘录试图以懒惰的方式构建，可能是无限的搜索树，其中每个键的值通过应用我们正在记忆的函数来计算 .

备忘录尝试可能并不完全符合您的要求，但这种技术很有可能适应您的目标 .
回复于 2024-04-27T11:42:23+08:00

相关问题