Data.Tree.LogTree

Typical usage (a 4-point FFT, using 2 radix-2, DIT stages):

-- Main
exeMain = do
    let tData = newTreeData [(2, False), (2, False)] [1.0, 0.0, 0.0, 0.0]
    let tree  = buildTree newFFTTree tData
    case tree of
      Left msg -> putStrLn msg
      Right  _ -> do
        -- If you're interested in the numerical result:
        let res = getEval tree
        putStrLn $ Result = tt ++ show res
        -- If you want to visualize how the computation breaks down:
        let (treePlot, legendPlot) = dotLogTree tree
        writeFile treeFileName   treePlot
        writeFile legendFileName legendPlot

And, to get easily viewable *.PNGs from the two files written, above:

>>> dot <treeFileName> -Tpng >tree.png

>>> dot <legendFileName> -Tpng >legend.png

Documentation

class (Show a, t ~ GenericLogTree a) => LogTree t a | t -> a where

A class of tree structures representing logarithmic decomposition of arbitrary radix and using either decimation-in-time (DIT), or decimation-in-frequency (DIF) approach (or, a mix of both).

Methods

evalNode :: (t, [Int]) -> [a]

Evaluates a node in a tree, returning a list of values of the original type. The supplied list of integers gives the index of the outer summation, for each step in the computational breakdown.

getTwiddles :: t -> [[a]]

Returns any necessary twiddle factors, for DIF decomposition.

calcTwiddles :: DecimationType -> Int -> Int -> [[a]]

The actual twiddle factor calculator.

getTwiddleStrs :: t -> [[String]]

Returns the string representations of the twiddle factors.

getCompNodes :: t -> [CompNode a]

Returns the complete list of computational nodes required, in order to evaluate the tree.

Instances

LogTree FFTTree (Complex PrettyDouble)

type GenericLogTree a = Tree (Maybe (a, [[a]]), [Int], Int, DecimationType)

A convenient type synonym, used as shorthand to specify the actual Tree type.

a is the data type of the original input list elements.

Tree type tuple, from left to right:

• Maybe (a, [[a]]) = original list element value, for leaf; Nothing, otherwise. The list of lists contains the accumulated twiddles.
• [Int] = starting indeces, in original input list, of children
• Int = index skip factor, in original input list, of children
• Bool = True, if decimation in frequency (DIF) was used to form children.

Notes:

• The radix of the decomposition at any level of a tree is equal to the number of children at that node (i.e. - length subForest), which should also equal the length of the second element in the Tree type tuple.

data TreeData a

Data structure used by tree builders.

Fields:

modes

A list of DecompositionModes

values

The list of values to be transformed.

Instances

Show a => Show (TreeData a)

newtype TreeBuilder t

Example: tree = buildTree newFFTTree tData

Note:

Please, don't use the TreeBuilder data constructor directly, in your client code, unless you are defining a new instance of typeclass LogTree. You will short circuit our data abstraction strategy, if you do this. This will expose your client code to potential breakage, in the future. (See the FFTTree.hs file for an example of how to create a new instance of typeclass, LogTree.)

Constructors

TreeBuilder

Fields

buildTree :: LogTree t a => TreeData a -> Either String t

data CompOp

Enumerates the possible computational operations performed by a computational node.

Constructors

Sum

Node sums its inputs.

Prod

Node multiplies its inputs.

Instances

Eq CompOp

type CompNodeOutput a = (CompOp, [a])

Our computational node type; tuple members are:

• type of operation (i.e. - CompOp)
• list of multiplicative coefficients (type a) to be applied to the inputs

type CompNode a = [CompNodeOutput a]

Completely defines a particular computational node, by specifying all of its outputs.

Each tuple in the list corresponds to a unique element of the output list.

data DecimationType

Enumerates the possible decimation styles of a computation breakdown stage.

Constructors

DIT

Decimation in Time.

DIF

Decimation in Frequency.

Instances

Eq DecimationType

Show DecimationType

LogTree FFTTree (Complex PrettyDouble)

type Radix = Int

A convenient type alias to help make the code more readable.

type DecompositionMode = (Radix, DecimationType)

A convenient type alias.

Each stage of a computation breakdown can be uniquely identified by a pair containing:

Radix

Typically, an integer defining the number of sub-computations being combined in this stage.

DecimationType

A flag giving the decimation style used in forming the list of elements in the sub-computations.

newTreeData

Arguments

:: [DecompositionMode]

Decomposition modes : (radix, DIF_flag).

-> [a]

Values for populating the tree.

-> TreeData a

Resultant data structure for passing to tree constructor.

Build a data structure suitable for passing to a tree constructor.

Example: tData = newTreeData [(2, DIT), (2, DIT)] [1.0, 0.0, 0.0, 0.0]

buildMixedRadixTree :: LogTree t a => TreeData a -> Either String t

NOT FOR USE BY GENERAL CLIENT CODE!

This has been exported, solely for use by definers of new instances of typeclass, LogTree. (See the FFTTree.hs file, for an example of how to do this.)