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

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
  ]