Recursive Block Diagram Specification

Recursive pattern matching, introduced and illustrated for computing factorial in §2.23 above, also gives a powerful way to define a block diagram recursively in terms of its partitions. For example, the following FAUST program defines Hadamard matrices of order $2^n$ where $n$ is a positive integer:

  bus(n) = par(i,n,_);  // There is si.bus(n) in the \FL s
//hmtx(2) = _,_ <: +,-; // scalar butterfly
  hmtx(2) = _,_ <: (bus(2):>_),(_,*(-1):>_) ; // prettier drawing
  hmtx(n) = bus(n) <: (bus(n):>bus(n/2)) , // vector butterfly
                 ((bus(n/2),(bus(n/2):par(i,n/2,*(-1)))) :> bus(n/2))
                 : (hmtx(n/2) , hmtx(n/2));
  process = hmtx(16);     // look at the diagram in the Faust Editor, e.g.

Other examples include Feedback Delay Networks (FDN) and the square waveguide mesh of order $2^n$ defined in the FAUST Libraries (see fdnrev0 in reverbs.lib and mesh_square() in misceffects.lib). An especially interesting example is the Fast Fourier Transform (fft defined in analyzers.lib).

See also basics.lib for examples of using recursion for a kind of list processing, such as in count and take.

Note that it is also possible to implement counterparts to par and seq using pattern matching (see the duplicate function on page 14 of the FaustQR.