是否存在以下属性的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)
空间运行
xs = iterate' f y
。如果满足条件(3),为什么还需要条件(2)?或者说:你实际上想表达的是条件(3)而不是条件(2)吗? - Daniel Wagneriterate' f y
可以需要 (2) 种状态,但如果您从未将elem'
应用于结果,则不必评估到那么远。 - GurkenglasData.IntTrie
的原因,尽管它看起来与您的属性有很大不同。但是,这个想法是拥有一个无限折叠,将元素逐步排序到一个快速访问结构中。如果a
和Int
之间存在平衡的同构,也许你可以利用它? - luqui