Trying to convert imperetive code to functional -Haskell

Question

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;
 }
 }

My Haskell code:

-- 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)])

• Lemming: 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.

Answer 1

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
 ]

• Lemming: Data.NumInstances.Tuple is an ugly hack. It would be more straightforward to use Data.Complex here.
• Gurkenglas: 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.
• Lemming: (**) on Complex numbers is a very bad idea. It is not well-defined and pretty slow. Better use cis (angle*t).
• Lemming: Also Complex division is not necessary. You can just write z * cis (-angle*t).