Implementing Division of Streams (where it's a stream of polynomial coefficients)

Question

Per this homework, I'm trying to implement a Fractional (Stream Integer) where the stream represents coefficients of polynomials:

where Q is defined as Q = (A'/b0) + x((1/b0)(A' − QB0)).

where A/B = Q,

That is, the first element of the result is A'/b0; the remainder is formed by computing A' − QB' and dividing each of its elements by b0

Note that A' == tail of A and same for B'

Here's my attempt:

divStreams :: Stream Integer -> Stream Integer -> Stream Integer
divStreams a@(Cons x xs) b@(Cons y ys) = 
    Cons (x `div` y) (streamMap ((1 `div` y) *) xs - (multStreams q ys) ) 
      where q = divStreams a b

with the following functions' definitions:

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

data Stream a = Cons a (Stream a)

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

Note that I defined Num (Stream Integer) where (+) == combineStreams (+)

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

Thanks to this answer that resolved an issue I had implementing multiplication of Streams.

Answer 1

There are a couple of cases where using where isn't gaining us anything. For instance, combineStreams can just be written as

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

Same goes for streamMap.

If you're not using combineStreams anywhere else, we can just write

instance Num (Stream Integer) where
    (Cons x xs) + (Cons y ys) = Cons (x + y) (xs + ys)

---

I just want to repeat the definition given in the homework, for clarity:

If \$A = a_0 + x A'\$ and \$B = b_0 + x B'\$, then \$A / B = Q\$, where \$Q\$ is defined as

\begin{align} Q = (a_0 / b_0) + x((1 / b_0)(A' - QB')). \end{align}

Your definition of divStreams is very close to this, but we can use the following trick where q refers to itself, just as in the formula above:

divStreams :: Stream Integer -> Stream Integer -> Stream Integer
divStreams (Cons x xs) (Cons y ys) = 
    let q = Cons (x `div` y) (streamMap ((1 `div` y) *) (xs - q * ys)) in q

assuming you have defined * to be multStreams.

Answer 2

Duplicate Call to divStreams

This duplication is already mentioned by @mjolka, but I want to add that this kind of duplication may lead to unnecessary function calls. You can fix it using let, but using where also works. Definite way to test this kind of problem (that I know of) is using Debug.Trace.trace. (In this case problem seems to be optimized away by the compiler, but you should not leave important behavior compiler implementation and version dependent)

import Debug.Trace

divStreams a@(Cons x xs) b@(Cons y ys) =
    "divStreams called" `trace` Cons (x `div` y) (streamMap ((1 `div` y) *) xs - (multStreams q ys)) 
      where q = divStreams a b

versus

divStreams a@(Cons x xs) b@(Cons y ys) =
    "divStreams called" `trace` q
      where q = Cons (x `div` y) (streamMap ((1 `div` y) *) xs - (multStreams q ys))

Misuse of div

streamMap ((1divy) *) only works for y=1 or y=-1. For other y the tail of the stream will all be zeros, even when it should not be.

Fixing it is easy: just replace streamMap ((1divy) *) with streamMap (divy).

Before we test, some definitions:

take' :: Int -> (Stream a) -> [a]
take' n _      | n <= 0 = []
take' n (Cons x xs)     = x : take' (n-1) xs

instance (Show a) => Show (Stream a) where
  show xs = show (take' 10 xs)

instance (Num a) => Num (Stream a) where
  (+) = combineStreams (+)
  negate = streamMap ((-1)*)

A simple test case is this:

divStreams' a@(Cons x xs) b@(Cons y ys) = q
      where q = Cons (x `div` y) (streamMap (`div` y) xs - (multStreams q ys))
ones = Cons 1 ones
twos = Cons 2 twos
onesTimesTwos = multStreams ones twos
ones' = divStreams onesTimesTwos twos
ones'' = divStreams' onesTimesTwos twos

> streamMap ((1 `div` 2) *) twos
[0,0,0,0,0,0,0,0,0,0]
> streamMap (`div` 2) twos
[1,1,1,1,1,1,1,1,1,1]
>ones'
[1,-2,2,-2,2,-2,2,-2,2,-2]-- expected 1, 1, 1, 1, ....

>ones''
[1,0,1,0,1,0,1,0,1,0] -- expected 1, 1, 1, 1, ....

oops. A bug still remains.