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

Question

假设我们正在遍历图表并希望快速确定之前是否已经看过某个节点.我们有一些先决条件.

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

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

我想要一个包含两个函数的数据结构; 添加(添加遇到的整数)和查找(检查是否添加了整数).两者都应该优选地将O(n)时间摊销以进行N次重复.

这可能吗？

Answer 1

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

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