From 4ba347ccb31b5a064a37367ce218f77c7532e9d8 Mon Sep 17 00:00:00 2001
From: Francis Russell <francis@unchartedbackwaters.co.uk>
Date: Wed, 17 Apr 2013 15:36:13 +0100
Subject: [PATCH] Construct padded DFT.

---
 LTA/Symbolic.hs |  7 +++++++
 src/Main.hs     | 23 ++++++++++++++++++-----
 2 files changed, 25 insertions(+), 5 deletions(-)

diff --git a/LTA/Symbolic.hs b/LTA/Symbolic.hs
index 107d3bd..80939ee 100644
--- a/LTA/Symbolic.hs
+++ b/LTA/Symbolic.hs
@@ -4,10 +4,12 @@ module LTA.Symbolic
   ( Expr(..)
   , Cond(..)
   , Constant(..)
+  , ContainsSymbols(..)
   , Literal(..)
   , CompareOp(..)
   , UnaryFunction(..)
   , buildConditional
+  , findUniqueSymbol
   , pow
   , simplify
   , (~==)
@@ -222,6 +224,11 @@ instance ContainsSymbols Cond where
     Or e1 e2 -> Set.union (findSymbols e1) (findSymbols e2)
     Not e -> findSymbols e
 
+findUniqueSymbol :: (ContainsSymbols e) => String -> e -> String
+findUniqueSymbol prefix expr = 
+  head [n | n <- generateNames, Set.notMember n syms ] where
+    syms = findSymbols expr
+    generateNames = [prefix ++ "_" ++ show n | n <- [0::Integer ..]]
 
 simplify :: Expr -> Expr
 simplify (Sum pairSeq) = rebuild $ normalise pairSeq
diff --git a/src/Main.hs b/src/Main.hs
index 952e49d..b39cd82 100644
--- a/src/Main.hs
+++ b/src/Main.hs
@@ -2,8 +2,20 @@ module Main (main) where
 
 import LTA.Symbolic
 
+data Matrix 
+ = Matrix Expr Expr Expr
+ deriving(Eq, Ord, Show)
+
+multiply :: Matrix -> Matrix -> Matrix
+multiply (Matrix aRows aCols aExpr) (Matrix bRows bCols bExpr) = 
+  Matrix aRows bCols $ Summation sumVar 0 aCols (aExpr' * bExpr') where
+    sumVar = findUniqueSymbol "sum" (aExpr * bExpr)
+    aExpr' = rename "col" sumVar aExpr
+    bExpr' = rename "row" sumVar bExpr
+
 main :: IO()
-main = putStrLn . show $ dft (IntegerSymbol "N")
+main = putStrLn . show $ (pad size) `multiply` (dft size) where
+  size = IntegerSymbol "N"
 
 row :: Expr
 row = IntegerSymbol "row"
@@ -20,14 +32,15 @@ i = Constant ImaginaryUnit
 pi :: Expr
 pi = Constant Pi
 
-dft :: Expr -> Expr
-dft size = pow e ((- i * 2 * Main.pi * row * col) / size)
+dft :: Expr -> Matrix
+dft size = Matrix size size $ pow e ((- i * 2 * Main.pi * row * col) / size)
 
 isEven :: Expr -> Cond
 isEven n = (n `Mod` 2) ~== 0
 
-pad :: Expr -> Expr
-pad size = Conditional (isEven size) (evenPad size) (oddPad size)
+pad :: Expr -> Matrix
+pad size = 
+  Matrix (2*size) size $ Conditional (isEven size) (evenPad size) (oddPad size)
 
 evenPad :: Expr -> Expr
 evenPad size = buildConditional 0 conditions where
-- 
2.47.3