haskell - 数据结构请求 : Lazily infinite set

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)空间

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)

(中间集算作分配空间吗？如果你需要平衡它们，你甚至可以在线性空间中做有限集吗？)