实现多项式乘法哈斯克尔

Question

我定义为多项式算法的一些功能

为了方便调试，我做多项式列表：

[5,3,7] -> 5 + 3*x + 7*x^2 

在这里，我得到的功能add已经工作：

add [1,9,7] [9,3] == [10,12,7] 

但我有麻烦mul：

mul []  _ = [0] 
mul (x : xs) ys = add (map (*x) ys) (mul (0 : xs) ys) 

正如我想象：

[4,5,6] * [1,2,3] = 4*[1,2,3] + [0,4,6]*[1,2,3] 

它需要永远评价mul [1] [1,2,3]，我无法找出什么地方错了。

Answer 1

mul []  _ = [0] 
mul (x : xs) ys = add (map (*x) ys) (mul (0 : xs) ys) 

让我们来看看发生了什么，当你评估mul [1] [1,2,3]：

mul (1:[]) [1,2,3] 
-> add (map (*1) [1,2,3]) (mul (0:[]) [1,2,3]) 
-> add [1,2,3] (mul [0] [1,2,3]) 
-> add [1,2,3] (mul (0:[]) [1,2,3]) 
-> add [1,2,3] (add (map (*0) [1,2,3]) (mul (0:[]) [1,2,3])) 
-> add [1,2,3] (add [0,0,0] (mul [0] [1,2,3])) 

每次取出head，另一head（0）追加到它，因此，你的第一个列表的长度（第一个参数mul）永远不会改变。

所以没有办法达到退出条件（first_list == []）。

为了解决这个问题，追加0的mul外：

mul []  _ = [0] 
mul (x : xs) ys = add (map (*x) ys) (0 : (mul (xs) ys)) 

或也许这是更接近你的直觉：

mul xs ys = if all (==0) xs 
       then [0] 
       else add (map (*(head xs)) ys) (0 : (mul (tail xs) ys))