0

我正在尝试使用 Haskell 中的分而治之方法编写 Karatsuba 算法。我用合并排序算法做到了，但在这里无法弄清楚，在这一点上有点尴尬。

我的主要功能如下所示：

dz test end divide combine x = 
   if test x then end x
   else combine(map(dz test end divide combine) (divide x))

我测试它的值1234和5678: dz test end divide combine [1234, 5678,2]。

所以我必须编写,test和end函数。dividecombine

lengthNumb x = length . show $ x
test (x:x1:xs) = (lengthNumb x) < 4 || (lengthNumb x1) < 4
end (x:y:z:xs) = [x * y, z]

这很简单。我只是检查我想要相乘的两个数字是否至少有 4 位数字。如果不是，我只使用简单的乘法和进位m值。我知道 Karatsuba 对于更大的数字效果更好，但这仅用于测试目的。

divide [] = []
divide (x:x1:x2:xs) = 
   let y1 = x `div` 10^x2
     y2 = x `mod` 10^x2
     y3 = x2 `div` 2
     z1 = x1 `div` 10^x2
     z2 = x1 `mod` 10^x2
   in [[y1,y2,y3],[z1,z2,y3],[y1+y2, z1+z2, y3]]

combine [[x, x1],[y,y1],[z,z1]] = x * 10^(2*x1) + y + (z - x - y) * 10^x1

有人告诉我这个combine函数应该只做最后的乘法。所以我想它应该得到三个数字作为输入（每个都有它们的m值），然后还做必要的减法（z-x-y），因为我不能在divide.

但这是错误的。我收到一个错误：

Occurs check: cannot construct the infinite type: a ~ [a]
  Expected type: [[a]] -> [a]

  Actual type: [[[a]]] -> [a]

我认为这是combine函数参数的问题，但我不知道如何解决。我还认为，如何协同工作可能存在问题，combine因为在之前的一次迭代中，乘法的最终结果是错误的。divide

4

0 回答 0