计算复杂的多项式值

Question

我想在 haskell.

中的给定点计算复数多项式的值

多项式以 ((Int,Int),Int) 个元素的列表形式给出，其中一对 (Int,Int) 代表商的实部和虚部，其余 Int 代表度数。因此，复数点 x 中多项式的值计算为 a_i*(x^t) 的总和，其中 a_i 是第 i 次商和 t 度数。

这是我的 haskell 代码：

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)

+%、*% 和 ^% 只不过是对复数定义的运算 +、* 和 ^类型 Komp.

拥抱可以很好地加载，但执行：

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

抛出错误：

ERROR - Control Stack Overflow

我不知道为什么会这样，也不知道如何调试。

Answer 1

我至少发现了两个错误。导致您问题的原因是 (^%) 的基本情况太高，因此

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

通过将基本案例更改为

来修复它

k ^% 0 = (1, 0)

第二个是你没有 vredKompPol 的基本情况，你可以通过添加像

这样的子句来解决这个问题

vredKompPol [] _ = (0, 0)

通过这两个更改，我得到：

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

我觉得很合适。

Answer 2

问题是您的 %^ 实现仅针对 n >= 1 定义，但您试图将其与 n = 0 一起使用，这永远不会达到基本情况（n = 1).

现在，hugs 已经停止开发，所以我建议改用 ghci。在ghci中，你可以像这样调试类似的问题：

[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.

设置标志以启用 Ctrl-c 中断:

*Main> :set -fbreak-on-error

跟踪有问题的函数：

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

片刻之后，按Ctrl-c停止执行。

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

: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)
...

使用 :back 向上移动执行历史，以便使用 :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 = _

这里没什么有趣的（可能是因为它是按下 Ctrl-c 时正在执行的函数）。上一步再试：

[-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>

因此，它在 n = -12390 的第 10 行执行。这表明非终止递归存在问题。

计算复杂的多项式值

Computing complex polynom value

haskell

complex-numbers

hugs