Functional Pearl: Perfect trees and bit−reversal permutations
A famous algorithm is the Fast Fourier Transform, or 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 othe...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Published: |
2000
|
| _version_ | 1797056161209384960 |
|---|---|
| author | Hinze, R |
| author_facet | Hinze, R |
| author_sort | Hinze, R |
| collection | OXFORD |
| description | A famous algorithm is the Fast Fourier Transform, or 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. |
| first_indexed | 2024-03-06T19:19:29Z |
| format | Journal article |
| id | oxford-uuid:1994c37b-fef3-4a8b-930b-4ee29d8dca8f |
| institution | University of Oxford |
| last_indexed | 2024-03-06T19:19:29Z |
| publishDate | 2000 |
| record_format | dspace |
| spelling | oxford-uuid:1994c37b-fef3-4a8b-930b-4ee29d8dca8f2022-03-26T10:49:41ZFunctional Pearl: Perfect trees and bit−reversal permutationsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:1994c37b-fef3-4a8b-930b-4ee29d8dca8fDepartment of Computer Science2000Hinze, RA famous algorithm is the Fast Fourier Transform, or 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. |
| spellingShingle | Hinze, R Functional Pearl: Perfect trees and bit−reversal permutations |
| title | Functional Pearl: Perfect trees and bit−reversal permutations |
| title_full | Functional Pearl: Perfect trees and bit−reversal permutations |
| title_fullStr | Functional Pearl: Perfect trees and bit−reversal permutations |
| title_full_unstemmed | Functional Pearl: Perfect trees and bit−reversal permutations |
| title_short | Functional Pearl: Perfect trees and bit−reversal permutations |
| title_sort | functional pearl perfect trees and bit reversal permutations |
| work_keys_str_mv | AT hinzer functionalpearlperfecttreesandbitreversalpermutations |