Perfect trees and bit-reversal permutations
Perfect trees and bit-reversal permutations
复制标题
完美树和位反转排列
DOI：
10.1017/s0956796800003701
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
R. Hinze
中科院分区：
文献类型：
--
作者：
R. Hinze
一种众所周知的算法是快速傅立叶变换（FFT）。FFT算法的有效迭代版本作为第一步执行输入列表的位反转置换。位反转置换交换其索引具有彼此相反的二进制表示的元素。使用摊销的方法，这个操作可以在随机存取机器上以线性时间运行。一个有趣的问题是，线性时间实现是否在指针机器上也是可行的，也就是说，在纯函数设置中。我们表明，这个问题的答案是肯定的。在得出一个解决方案，我们采用了几个先进的编程语言的概念，如嵌套的数据库，相关的折叠和展开运算符，秩2类型和多态递归。
One well known algorithm is the Fast Fourier Transform (FFT). An efficient iterative version of the FFT algorithm performs as a first step a bit-reversal permutation of the input list. The bit-reversal permutation swaps elements whose indices have binary representations that are the reverse of each other. Using an amortized approach, this operation can be made to run in linear time on a random-access machine. An intriguing question is whether a linear-time implementation is also feasible on a pointer machine, that is, in a purely functional setting. We show that the answer to this question is in the affirmative. In deriving a solution, we employ several advanced programming language concepts such as nested datatypes, associated fold and unfold operators, rank-2 types and polymorphic recursion.