乘法流（表示多項式係數）

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)