algorithm - 函数式语言的快速元素查找(Haskell)

Question

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

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

以纯函数方式执行此操作的任何想法？(不允许使用哈希表或数组)。

我想要一个包含两个函数的数据结构；添加(添加遇到的整数)和查找(检查是否添加了整数)。两者都应该最好将 O(n) 时间摊销为 N 次重复。

这可能吗？

Answer 1

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

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