关于希尔伯特立方体的维基百科文章包括对希尔伯特曲线上任意点的任意索引进行编码/解码的函数。这些算法不是恒定时间的。是否有一个恒定时间算法,给定曲线上的一个实际点(可能还有一些所需的状态),生成下一个点(和下一个状态)?
形式上,我想要一个 typeState
和一个 tuple (initialState, nextState) :: (State, State -> ((Nat, Nat), State)
,这样每个应用程序nextState
都会为我们提供希尔伯特曲线的下一个点,并且这nextState
是最优的,这可能不是 Wikipedia 上提供的算法的情况,因为它可能会错过我们在这里拥有增量计算的机会。插图:
data State = _
initialState :: State
initialState = _
-- This must be optimal
nextState :: State -> ((Nat, Nat), State)
nextState = _
-- Returns the `nth point` of the hilbert curve
hilbertPoint :: Nat -> (Nat, Nat)
hilbertPoint n = iterate (snd.nextState) initialState !! n