数据结构需求：惰性无限集合

Question

是否存在以下属性的F :: * -> *、iterate' :: Ord a => (a -> a) -> a -> F a和elem' :: Ord a => Int -> a -> F a -> Bool？

• elem x (take n (iterate f y)) ⇒ elem' n x (iterate' f y) ⇒ elem x (iterate f y)

• elem' n x (iterate' f y)以O(n * log n)时间和O(n)空间运行

• elem' n x xs以O(log n)时间和O(1)空间运行

- Gurkenglas

---

条件（3）看起来比条件（2）更强，因为我们可以选择 xs = iterate' f y。如果满足条件（3），为什么还需要条件（2）？或者说：你实际上想表达的是条件（3）而不是条件（2）吗？ - Daniel Wagner

属性中的自由变量不需要额外的时间或空间。iterate' f y 可以需要 (2) 种状态，但如果您从未将 elem' 应用于结果，则不必评估到那么远。 - Gurkenglas

当然，那是一个非常明智的立场。明白了，感谢您准确的回答。 - Daniel Wagner

我很好奇，如果我们有先前的知识，即“迭代f”是均匀分布的，是否有巧妙的解决方案。 - jberryman

这种东西正是我为之编写 Data.IntTrie 的原因，尽管它看起来与您的属性有很大不同。但是，这个想法是拥有一个无限折叠，将元素逐步排序到一个快速访问结构中。如果 a 和 Int 之间存在平衡的同构，也许你可以利用它？ - luqui

Answer 1

import qualified Data.Set as S

type F x = [S.Set x]

iterate' f
  = map head
  . evalState (traverse (state . splitAt) (iterate (*2) 1))
  . scanl (flip S.insert) S.empty
  . iterate f

elem' n x xs = S.member x $ xs !! (ceiling (logBase 2 (fromIntegral n)) - 1)

中间集合是否算作已分配空间？如果需要平衡，即使只有有限的空间，也能在线性空间中完成有限集吗？

- Gurkenglas

---

这个解决方案（以及我能想象到的其他所有解决方案）都没有满足条件（2），因为它需要至少 O(n * log n) 的空间来存储最大集合。 - Cirdec

@Cirdec 嗯，为什么？一个有n个元素的集合不是只使用O(n)的空间吗？我认为平衡二叉搜索树可以实现这一点。 - chi

也许如果你先将迭代分成指数增长的部分，就不需要那么多中间集合，空间可以保持O(n)。 - chi

S.fromList 和 S.union 的空间复杂度是线性的吗？ 我只看到时间复杂度的需求。 - Gurkenglas