乘法流（表示多项式系数）

Question

对于此2013 homework，我试图乘以2个流。

xStream :: Stream Integer 
xStream = Cons 0 (Cons 1 $ streamRepeat 0) 

instance Num (Stream Integer) where 
    fromInteger x = Cons x $ streamRepeat 0 
    negate  = streamMap (* (-1)) 
    (+) xs ys  = combineStreams (+) xs ys 
    (*) xs ys  = multStreams xs ys 
    abs   = streamMap abs 

这里的教授对如何实现上述流的倍增帮助：

Multiplication is a bit trickier. Suppose A = a0 + xA` and B = b0 + 
xB0 are two generating functions we wish to multiply. We reason as 
follows: AB = (a0 + xA`)B 
      = a0B + xA`B  
      = a0(b0 + xB0) + xA`B 
      = a0b0 + x(a0B0 + A`B) 

这里是我的尝试：

multStreams :: Stream Integer -> Stream Integer -> Stream Integer 
multStreams (Cons x xs) b@(Cons y ys) = addXY + rest 
    where addXY = Cons (x + y) $ streamRepeat 0 
     rest = (xStream *) $ (streamMap (*x) ys + (xs * b)) 

以下定义：

data Stream a = Cons a (Stream a) 

streamRepeat :: a -> Stream a 
streamRepeat x = Cons x (streamRepeat x)  

streamMap :: (a -> b) -> Stream a -> Stream b 
streamMap f (Cons x xs) = Cons (f x) rest 
    where rest = streamMap f xs 

combineStreams :: (a -> b -> c) -> Stream a -> Stream b -> Stream c 
combineStreams f (Cons x xs) (Cons y ys) = Cons (f x y) rest 
    where rest = combineStreams f xs ys 

请注意，xStream与x相同，每。

当我尝试上述实现时，我致电multStreams不终止。

请帮我理解我的上述multStream函数有什么问题 - 无论是在实现中，还是我甚至实现了教授对乘法的正确解释。

Answer 1

最根本的问题是，你的multStreams定义直接Stream在rest的定义，这是不想要的结果由给定的推理使用(*)。

如果考虑方程AB = a0b0 + x(a0B0 + A'B)，它会告诉你的AB第一项应该是什么确切地说a0b0是一个常数，即第一项的一部分，并且流中的每个其他项由x相乘，即不第一学期的一部分。

它还告诉你，AB来自a0B0 + A'B的剩余条款 - 因为有Cons换挡同时，它通过一个等同于x multipltying。

与你所做的主要区别在于，输出流的第一个元素可以在没有任何对(*)的递归调用的情况下构建，即使其余元素使用一个。

所以这样的事情应该工作：

multStreams :: Stream Integer -> Stream Integer -> Stream Integer 
multStreams (Cons x xs) b@(Cons y ys) = 
    Cons (x * y) (streamMap (*x) ys + multStreams xs b)