假设我们正在遍历一个图并想快速确定一个节点之前是否见过。我们有一些先决条件。
- 节点已用整数值 1..N 标记
- 图是用具有邻接表的节点实现的
- 从 1..N 开始的每个整数值都出现在大小为 N 的图中
以纯函数方式执行此操作的任何想法?(不允许使用哈希表或数组)。
我想要一个包含两个函数的数据结构;添加(添加遇到的整数)和查找(检查是否添加了整数)。两者都应该最好将 O(n) 时间摊销为 N 次重复。
这可能吗?
最佳答案
您可以使用 Data.Set .您可以通过使用 insert
从旧集合创建新集合并传递新集合来添加元素。您使用 member
查找元素是否是集合的成员。两个操作都是 O(log n)。
也许,您可以考虑使用状态 monad 来线程化集合的传递。
关于algorithm - 函数式语言的快速元素查找(Haskell),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/288157/