Perfect trees and bit-reversal permutations

@article{citeulike:2883447, abstract = {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.}, author = {Hinze, Ralf }, citeulike-article-id = {2883447}, doi = {10.1017/S0956796800003701}, journal = {Journal of Functional Programming}, keywords = {fold, haskell, nested-datatypes, performance, rank-2-polymorphism, unfold}, number = {03}, pages = {305--317}, posted-at = {2008-06-11 18:19:57}, priority = {3}, title = {Perfect trees and bit-reversal permutations}, url = {http://journals.cambridge.org/action/displayAbstract?fromPage=online\&aid=54527}, volume = {10}, year = {2000} }

TY - JOUR ID - citeulike:2883447 L3 - citeulike-article-id:2883447 TI - Perfect trees and bit-reversal permutations JF - Journal of Functional Programming VL - 10 IS - 03 SP - 305 EP - 317 N2 - 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. KW - fold KW - haskell KW - nested-datatypes KW - performance KW - rank-2-polymorphism KW - unfold AU - Hinze, Ralf PY - 2000/// UR - http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=54527 ER -