Task

Calculate the   FFT   (Fast Fourier Transform)   of an input sequence.

The most general case allows for complex numbers at the input
and results in a sequence of equal length, again of complex numbers.
If you need to restrict yourself to real numbers, the output should
be the magnitude   (i.e.:   sqrt(re2 + im2))   of the complex result.

The classic version is the recursive Cooley–Tukey FFT. Wikipedia has pseudo-code for that.
Further optimizations are possible but not required.




 
 
1) the function fft
 
{def fft   
 {lambda {:s :x}
  {if {= {list.length :x} 1}
   then :x
   else {let { {:s :s}
               {:ev {fft :s {evens :x}} }
               {:od {fft :s {odds  :x}} } }
        {let { {:ev :ev} {:t {rotate :s :od 0 {list.length :od}}} }
        {list.append {list.map Cadd :ev :t}
                     {list.map Csub :ev :t}} }}}}}
 
{def rotate 
 {lambda {:s :f :k :N}
  {if {list.null? :f}
   then nil
   else {cons {Cmul {car :f} {Cexp {Cnew 0 {/ {* :s {PI} :k} :N}}}}
              {rotate :s {cdr :f} {+ :k 1} :N}}}}}
 
2) functions for lists
 
We add to the existing {lambda talk}'s list primitives a small set of functions required by the function fft.
 
{def evens
 {lambda {:l}
  {if {list.null? :l}
   then nil
   else {cons {car :l} {evens {cdr {cdr :l}}}}}}}
 
{def odds
 {lambda {:l}
  {if {list.null? {cdr :l}}
   then nil
   else {cons {car {cdr :l}} {odds {cdr {cdr :l}}}}}}}
 
{def list.map
 {def list.map.r 
  {lambda {:f :a :b :c}
   {if {list.null? :a}
    then :c
    else {list.map.r :f {cdr :a} {cdr :b} 
                        {cons {:f {car :a} {car :b}} :c}} }}}
 {lambda {:f :a :b}
  {list.map.r :f {list.reverse :a} {list.reverse :b} nil}}}
 
{def list.append
 {def list.append.r
  {lambda {:a :b}
   {if {list.null? :b}
    then :a
    else {list.append.r {cons {car :b} :a} {cdr :b}}}}}
 {lambda {:a :b}
  {list.append.r :b {list.reverse :a}} }}
 
3) functions for Cnumbers
 
{lambda talk} has no primitive functions working on complex numbers. We add the minimal set required by the function fft.
 
{def Cnew
 {lambda {:x :y}
  {cons :x :y} }} 
 
{def Cnorm
 {lambda {:c}
  {sqrt {+ {* {car :c} {car :c}}
           {* {cdr :c} {cdr :c}}}} }}
 
{def Cadd
 {lambda {:x :y}
  {cons {+ {car :x} {car :y}}
        {+ {cdr :x} {cdr :y}}} }}
 
{def Csub
 {lambda {:x :y}
  {cons {- {car :x} {car :y}}
        {- {cdr :x} {cdr :y}}} }}
 
{def Cmul
 {lambda {:x :y}
  {cons {- {* {car :x} {car :y}} {* {cdr :x} {cdr :y}}}
        {+ {* {car :x} {cdr :y}} {* {cdr :x} {car :y}}}} }}
 
{def Cexp
  {lambda {:x}
   {cons {* {exp {car :x}} {cos {cdr :x}}}
         {* {exp {car :x}} {sin {cdr :x}}}} }}
 
{def Clist
 {lambda {:s}
  {list.new {map {lambda {:i} {cons :i 0}} :s}}}}
 
4) testing
 
Applying the fft function on such a sample (1 1 1 1 0 0 0 0) where numbers have been promoted as complex
 
{list.disp {fft -1 {Clist 1 1 1 1 0 0 0 0}}} ->
 
(4 0) 
(1 -2.414213562373095) 
(0 0) 
(1 -0.4142135623730949) 
(0 0) 
(0.9999999999999999 0.4142135623730949) 
(0 0) 
(0.9999999999999997 2.414213562373095)
 
A more usefull example can be seen in http://lambdaway.free.fr/lambdaspeech/?view=zorg
 
 