Learning Haskell and found an error in some sample code

Question

When I learn a new language, the first thing I do is to read through a Fast Fourier Transform implementation and try to get it to work. It's an algorithm that I'm fairly familiar with - so it helps me to understand how the language works.

Currently, I'm reading through this implementation by Roman Cheplyaka. I have followed the algorithm very closely now and everything seems to work as intended, but the following piece of code throws a bunch of errors for me: (specifically, the squareMap part throws the error)

evalFourier coeffs pts = do
  let
    squares = nub $ u_sqr <$> pts -- values of x^2
    (even_coeffs, odd_coeffs) = split coeffs
  even_values <- evalFourier even_coeffs squares
  odd_values <- evalFourier odd_coeffs squares

  let
    -- a mapping from x^2 to (A_e(x^2), A_o(x^2))
    square_map =
      Map.fromList
      . zip squares
      $ zip even_values odd_values

    -- evaluate the polynomial at a single point
    eval1 :: U -> Writer (Sum Int) (Complex a)
    eval1 x = do
      let (ye,yo) = (square_map Map.! u_sqr x)
          r = ye + toComplex x * yo
      tell $ Sum 2 -- this took two arithmetic operations
      return r

  mapM eval1 pts

Note that Map is short for Data.Map and here are some non-standard library functions that were defined in the implementation:

-- | U q corresponds to the complex number exp(2 i pi q)
newtype U = U Rational
  deriving (Show, Eq, Ord)

-- | Convert a U number to the equivalent complex number
toComplex :: Floating a => U -> Complex a
toComplex (U q) = mkPolar 1 (2 * pi * realToFrac q)

-- | Smart constructor for U numbers; automatically performs normalization
mkU :: Rational -> U
mkU q = U (q - realToFrac (floor q))

-- | Raise a U number to a power
uPow :: U -> Integer -> U
uPow (U q) p = mkU (fromIntegral p*q)

-- | Square a U number
uSqr :: U -> U
uSqr x = uPow x 2

Here is the error that shows after I run stack build:

src\FFT.hs:43:13: error:
    * Couldn't match type `a' with `a1'
      `a' is a rigid type variable bound by
        the type signature for:
          evalFourier :: forall a.
                         RealFloat a =>
                         [Complex a] -> [U] -> Writer (Sum Int) [Complex a]
        at src\FFT.hs:(19,1)-(22,35)
      `a1' is a rigid type variable bound by
        the type signature for:
          eval1 :: forall a1. U -> Writer (Sum Int) (Complex a1)
        at src\FFT.hs:38:9-50
      Expected type: WriterT
                       (Sum Int) Data.Functor.Identity.Identity (Complex a1)
        Actual type: WriterT
                       (Sum Int) Data.Functor.Identity.Identity (Complex a)
    * In a stmt of a 'do' block: return r
      In the expression:
        do let (ye, yo) = (squareMap Map.! uSqr x)
               r = ye + toComplex x * yo
           tell $ Sum 2
           return r
      In an equation for `eval1':
          eval1 x
            = do let (ye, yo) = ...
                     ....
                 tell $ Sum 2
                 return r
    * Relevant bindings include
        r :: Complex a (bound at src\FFT.hs:41:17)
        ye :: Complex a (bound at src\FFT.hs:40:18)
        yo :: Complex a (bound at src\FFT.hs:40:21)
        eval1 :: U -> Writer (Sum Int) (Complex a1)
          (bound at src\FFT.hs:39:9)
        squareMap :: Map.Map U (Complex a, Complex a)
          (bound at src\FFT.hs:33:9)
        oddValues :: [Complex a] (bound at src\FFT.hs:30:5)
        (Some bindings suppressed; use -fmax-relevant-binds=N or -fno-max-relevant-binds)
   |
43 |             return r
   |             ^^^^^^^^


--  While building custom Setup.hs for package FastFourier-0.1.0.0 using:
      C:\sr\setup-exe-cache\x86_64-windows\Cabal-simple_Z6RU0evB_2.0.1.0_ghc-8.2.2.exe --builddir=.stack-work\dist\5c8418a7 build lib:FastFourier exe:FastFourier-exe --ghc-options " -ddump-hi -ddump-to-file -fdiagnostics-color=always"
    Process exited with code: ExitFailure 1

Can anyone please point out what is causing the error I'm seeing here? I have a feeling this error has something to do with the line let (ye,yo) = (square_map Map.! u_sqr x). Thanks.

Should note that numeric code probably isn't the easiest way to get used to Haskell as most popular algorithm rely on mutable buffers - which you can get in Haskell, but they're not a first class feature. — Cubic
– Cubic, Commented Jun 30, 2018 at 20:14

melpomene · Accepted Answer · 2018-06-30 20:34:03Z

5

It looks like you're missing two pieces from the linked code:

{-# LANGUAGE ScopedTypeVariables #-}

at the top and

evalFourier
  :: forall a . RealFloat a
  => [Complex a] -- ^ polynomial coefficients, starting from a_0
  -> [U] -- ^ points at which to evaluate the polynomial
  -> Writer (Sum Int) [Complex a]

as the type signature for evalFourier.

Without ScopedTypeVariables, the two a type variables (in the type of evalFourier and the nested eval1 :: U -> Writer (Sum Int) (Complex a)) are independent. In particular, the type of eval1 specifies a fully general result type, which is not matched by the function body.

With ScopedTypeVariables, the inner a in the type of eval1 refers to the outer a defined by forall a. ....

The {-# LANGUAGE ... #-} construct is a pragma (a compiler directive).

The LANGUAGE pragma enables language extensions.

See Language.Haskell.Extension for a list of language extensions understood by GHC, and in particular -XScopedTypeVariables for ScopedTypeVariables.

edited Jun 30, 2018 at 20:34

answered Jun 30, 2018 at 20:13

melpomene

86.2k8 gold badges96 silver badges155 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Floyd Everest Over a year ago

Well you just killed two birds with one stone there! This definitely fixes the program, but I still have a while to go before I fully understand the type systems in Haskell. While you're here, could you explain to me what the {-# LANGUAGE ScopedTypeVariables #-} line actually does in general? Also, what else can we write in place of 'ScopedTypeVariables' and what do they do?

melpomene Over a year ago

@FloydEverest I added some links.

Floyd Everest Over a year ago

Thank you so much! I'll have to remember to upvote everything the day I get 15 points - I'm new here from math.Stackexchange. Again, thank you so much for your guidance!

Collectives™ on Stack Overflow

Learning Haskell and found an error in some sample code

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related