數據結構請求：懶惰無限集

是否有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)

來源

2016-12-17 Gurkenglas

條件（3）看起來比條件（2）強得多，因爲我們可以選擇'xs = iterate'f y'。爲滿足條件（3），爲什麼需要條件（2）？或者：你實際上*作爲你的條件而不是條件（3）意味着什麼？ –

屬性中的自由變量不會佔用任何額外的時間或空間。 'iterate'f y'是「允許」需要什麼（2）的狀態，但是如果你從未對結果應用'elem''則不必評估那麼遠。 – Gurkenglas

當然，這是一個非常明智的立場。理解並感謝您的答案。 –

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)

（是否將中間集計爲分配空間？如果需要平衡它們，你甚至可以在線性空間中做有限集合嗎？）

來源

2016-12-17 03:14:28 Gurkenglas

這個（以及我能想象的其他所有解決方案）都會忽略條件（2），因爲它至少需要'O（n * log n）'空間來存儲最大集合。 – Cirdec

@Cirdec嚴，爲什麼？具有n個元素的集合是否僅使用O（n）空間？我認爲平衡的BST實現了這一點。 – chi

也許如果你先迭代成指數增長的部分，你不需要這麼多的中間集合，並且空間可以保持O（n）。 – chi

數據結構請求：懶惰無限集

回答

相關問題