Computing complex polynom value

Question

I want to compute value of a complex polynomial at the given point, in haskell.

Polynomial is given as a list of ((Int,Int),Int) elements, where the pair (Int,Int) stands for real and imaginary unit of the quotient, and the remaining Int represents degree. Therefore, value of the polynomial in complex point x is computed as the sum of a_i*(x^t) where a_i is the ith quotient and t degree.

Here is my haskell code:

type Komp = (Int, Int)
(+%) :: Komp -> Komp -> Komp
(r1, i1) +% (r2, i2)    = (r1+r2, i1+i2)

(*%) :: Komp -> Komp -> Komp
(r1, i1) *% (r2, i2)    = (r1*r2 - i1*i2, r1*i2 + i1*r2)

(^%) :: Komp -> Int -> Komp
k ^% 1      = k
k ^% n      = (k ^% (n-1)) *% k

vredKompPol :: [(Komp,Int)] -> Komp -> Komp
vredKompPol ((k,s):poli) t  = k*%(t^%s) +% (vredKompPol poli t)

+%, *% and ^% are nothing more but operations +, * and ^ defined over complex numbers represented by the type Komp.

It loads fine with hugs, but execution:

Main> vredKompPol [((1,1),2),((1,1),0)] (0,0)

throws an error:

ERROR - Control Stack Overflow

which I don't know why it happens or how to debug it.

Answer 1

The problem is that your implementation of %^ is only defined for n >= 1, but you're trying to use it with n = 0, which never reaches the base case (n = 1).

Now, hugs is out of development so I would recommend using ghci instead. In ghci, you can debug similar problems like this:

[jakob:~]$ ghci foo.hs
GHCi, version 7.8.4: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( foo.hs, interpreted )
Ok, modules loaded: Main.

Set a flag to enable breaking on Ctrl-c:

*Main> :set -fbreak-on-error

Trace the problematic function:

*Main> :trace vredKompPol [((1,1),2),((1,1),0)] (0,0)

After a little while, press Ctrl-c to stop execution.

^CStopped at <exception thrown>
_exception :: e = _

:history shows the execution history.

[<exception thrown>] *Main> :history
-1  : *% (foo.hs:6:1-56)
-2  : ^% (foo.hs:10:15-31)
-3  : ^% (foo.hs:10:22-24)
-4  : ^% (foo.hs:(9,1)-(10,31))
-5  : ^% (foo.hs:10:16-25)
-6  : *% (foo.hs:6:1-56)
-7  : ^% (foo.hs:10:15-31)
-8  : ^% (foo.hs:10:22-24)
-9  : ^% (foo.hs:(9,1)-(10,31))
-10 : ^% (foo.hs:10:16-25)
-11 : *% (foo.hs:6:1-56)
-12 : ^% (foo.hs:10:15-31)
-13 : ^% (foo.hs:10:22-24)
-14 : ^% (foo.hs:(9,1)-(10,31))
-15 : ^% (foo.hs:10:16-25)
-16 : *% (foo.hs:6:1-56)
-17 : ^% (foo.hs:10:15-31)
-18 : ^% (foo.hs:10:22-24)
-19 : ^% (foo.hs:(9,1)-(10,31))
-20 : ^% (foo.hs:10:16-25)
...

Use :back to move up the execution history in order to inspect the arguments using :show bindings:

[<exception thrown>] *Main> :back
Logged breakpoint at foo.hs:6:1-56
_result :: Komp
[-1: foo.hs:6:1-56] *Main> :show bindings
_exception :: e = _
_result :: Komp = _

Nothing interesting here (probably because it's the function that was executing when Ctrl-c was pressed). Move up a step and try again:

[-1: foo.hs:6:1-56] *Main> :back
Logged breakpoint at foo.hs:10:15-31
_result :: Komp
k :: Komp
n :: Int
[-2: foo.hs:10:15-31] *Main> :show bindings
_exception :: e = _
n :: Int = -12390
k :: Komp = (0,0)
_result :: Komp = _
[-2: foo.hs:10:15-31] *Main> 

So, it's executing on line 10 with n = -12390. This suggests a problem with non-terminating recursion.

Answer 2

There are at least two bugs I spot. The one causing your problem is that your base case for (^%) is too high, so

> (1,1) ^% 0
*** Exception: stack overflow

Fix it by changing the base case to

k ^% 0 = (1, 0)

The second is that you have no base case for vredKompPol, which you can fix by adding a clause like

vredKompPol [] _ = (0, 0)

With these two changes, I get:

*Main> vredKompPol [((1,1),2),((1,1),0)] (0,0)
(1,1)

That looks right to me.