# Trying to convert imperetive code to functional -Haskell

I'm very new to Haskell and I was trying to implement a DFT which is very imperative into Haskell and I wanted to get a feedback. More specially how can I avoid so many helper functions and I avoid limiting to Double everywhere. Thank you.

My DFT algorithm:

 void dft(double[] inreal , double[] inimag, double[] outreal, double[] outimag) {
int n = inreal.length;
for (int k = 0; k < n; k++) {      // For each output element
double sumreal = 0;
double sumimag = 0;
for (int t = 0; t < n; t++) {  // For each input element
double angle = 2 * Math.PI * t * k / n;
sumreal +=  inreal[t] * Math.cos(angle) + inimag[t] * Math.sin(angle);
sumimag += -inreal[t] * Math.sin(angle) + inimag[t] * Math.cos(angle);
}
outreal[k] = sumreal;
outimag[k] = sumimag;
}
}


-- Length of the array
ownLength :: [t] -> Int
ownLength [] = 0
ownLength (_: xs) = 1 + ownLength xs

dft_resolve_nested :: [((Double, Double), Double)] -> Double -> Int -> [(Double, Double)]
dft_resolve_nested [] _ _ = []
dft_resolve_nested (((x, y), t) : xs) k n = do
let angle = 2.0 * pi * ( t) * ( k) / (fromIntegral n)
let sumreal = x * (cos angle) + y * (sin angle)
let sumimag = - x * (sin angle) + y * (cos angle)
(sumreal, sumimag) : (dft_resolve_nested xs k n)

tuples_sum :: [(Double, Double)] -> (Double, Double)
tuples_sum [] = (0, 0)
tuples_sum ((x1, y1) : xs) = do
let (x2, y2) = tuples_sum xs
(x1 + x2, y1 + y2)

dft_resolve ::  [((Double, Double), Double)] -> [(Double, Double)]
dft_resolve [] = []
dft_resolve ls = do
let n = ownLength ls
let (((x, y), k) : xs) = ls
let (xr, yr) = tuples_sum (dft_resolve_nested ls k n)
(xr, yr) : (dft_resolve xs)

dft :: [(Double, Double)] -> [(Double, Double)]
dft [] = []
dft ls = dft_resolve (zip ls [0..])

-- Main driver
main = do
print (dft [(1,2), (3,4)])

• You do not need to simulate a Complex type, Haskell provides Data.Complex. It also has the function cis which is the exponential function of a purely imaginary number. – Lemming Feb 10 '20 at 17:36

Why are you reimplementing length O_o?

dft_resolve_nested :: Double -> Int -> [((Double, Double), Double)] -> [(Double, Double)]
dft_resolve_nested _ _ [] = []
dft_resolve_nested k n (((x, y), t) : xs) = do
let angle = 2.0 * pi * t * k / fromIntegral n
let sumreal = x * cos angle + y * sin angle
let sumimag = - x * sin angle + y * cos angle
(sumreal, sumimag) : dft_resolve_nested k n xs

tuples_sum :: [(Double, Double)] -> (Double, Double)
tuples_sum [] = (0, 0)
tuples_sum ((x1, y1) : xs) = do
let (x2, y2) = tuples_sum xs
(x1 + x2, y1 + y2)

dft_resolve ::  [((Double, Double), Double)] -> [(Double, Double)]
dft_resolve [] = []
dft_resolve ls@((_, k) : xs) = do
let (xr, yr) = tuples_sum $dft_resolve_nested ls k$ length ls
(xr, yr) : dft_resolve xs

-- Main driver
main = print $dft_resolve$ zip [(1,2), (3,4)] [0..]


The explicit recursion can be done by library functions.

dft_resolve_nested :: Double -> Int -> ((Double, Double), Double) -> (Double, Double)
dft_resolve_nested k n ((x, y), t) = do
let angle = 2.0 * pi * t * k / fromIntegral n
sumreal = x * cos angle + y * sin angle
sumimag = - x * sin angle + y * cos angle
in (sumreal, sumimag)

tuples_sum :: (Double, Double) -> (Double, Double) -> (Double, Double)
tuples_sum (x1, y1) (x2, y2) = (x1 + x2, y1 + y2)

dft_resolve ::  [((Double, Double), Double)] -> (Double, Double)
dft_resolve ls@((_, k) : _) = foldr tuples_sum (0,0) $map (dft_resolve_nested k$ length ls) ls

-- Main driver
main = print $map dft_resolve$ tails $zip [(1,2), (3,4)] [0..]  Many of these names can be removed. You were also only ever restricted to Double by your own type signatures :). (You may want to tell it what Floating instance to use somewhere, though.) import Data.NumInstances.Tuple main :: IO () main = print [ sum [ ( x * cos angle + y * sin angle , -x * sin angle + y * cos angle ) | (t, (x, y)) <- ls , let angle = 2 * pi * t * k / genericLength ls ] | (k, ls) <- zip [0..]$ tails [(1,2), (3,4)]
]


Edit: Data.Complex specializes in this sort of math:

import Data.Complex

main :: IO ()
main = print
[ sum [z / cis angle ** t | (t, z) <- ls]
| (k, ls) <- zip [0..] \$ tails [1:+2, 3:+4]
, let angle = 2 * pi * k / genericLength ls
]

• Data.NumInstances.Tuple is an ugly hack. It would be more straightforward to use Data.Complex here. – Lemming Feb 10 '20 at 17:37
• DNT is a straightforward mechanical greedy refactoring step. DC is a perfect fit that usually doesn't come into play, and I will endeavour to associate it with trigonometry from here on out. – Gurkenglas Feb 11 '20 at 11:27
• (**) on Complex numbers is a very bad idea. It is not well-defined and pretty slow. Better use cis (angle*t). – Lemming Feb 11 '20 at 15:16
• Also Complex division is not necessary. You can just write z * cis (-angle*t). – Lemming Feb 11 '20 at 15:17