数据结构请求:Lazily无限集

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)

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