1
\$\begingroup\$

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)])
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ – Lemming Feb 10 '20 at 17:36
2
\$\begingroup\$

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
  ]
\$\endgroup\$
4
  • \$\begingroup\$ Data.NumInstances.Tuple is an ugly hack. It would be more straightforward to use Data.Complex here. \$\endgroup\$ – Lemming Feb 10 '20 at 17:37
  • \$\begingroup\$ 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. \$\endgroup\$ – Gurkenglas Feb 11 '20 at 11:27
  • \$\begingroup\$ (**) on Complex numbers is a very bad idea. It is not well-defined and pretty slow. Better use cis (angle*t). \$\endgroup\$ – Lemming Feb 11 '20 at 15:16
  • \$\begingroup\$ Also Complex division is not necessary. You can just write z * cis (-angle*t). \$\endgroup\$ – Lemming Feb 11 '20 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.