algorithm - 函数式语言的快速元素查找（Haskell）

Question

假设我们正在遍历一个图，并且想要快速确定一个节点之前是否出现过。我们有一些设定的先决条件。

1. 节点已用整数值 1..N 标记
2. 图是用具有邻接列表的节点实现的
3. 1..N 中的每个整数值都出现在图中，其大小为 N

以纯功能方式执行此操作的任何想法？（不允许哈希表或数组）。

我想要一个有两个函数的数据结构；add（添加遇到的整数）和查找（检查是否添加了整数）。两者都应该优选地花费 O(n) 时间来分摊 N 次重复。

这可能吗？

Answer 1

您可以使用Data.Set。您可以通过使用旧集合创建新集合insert并传递新集合来添加元素。您使用 查找元素是否是集合的成员member。这两个操作都是 O(log n)。

也许，您可以考虑使用 state monad 来线程化集合的传递。

Answer 2

函数式语言中的高效元素查找非常困难。Data.Set（如上所示）是使用二叉树实现的，该二叉树可以以纯功能方式构建，提供 O(log n) 中的查找操作。HashTables（不是纯粹的功能）将有 O(1)。

Answer 3

如果您不介意将代码包装在 IO monad 中，请查看judy hashtables 。

Answer 4

我相信 Data.BitSet 可能是 O(n)。