content: module Stream (Stream, carry, addStream, rationalToStream,
                  streamToFloat, addFiniteStream, negate', average) where
  
  import Data.Ratio
  
  
  type Digit = Integer
  type Stream = [Integer]
  
  
  
  -- Convert from a Rational fraction to its stream representation
  rationalToStream :: Rational -> Stream
  rationalToStream x
          |t<1            = 0:rationalToStream t
          |otherwise      = 1:rationalToStream (t-1)
          where t = 2*x
  
  
  
  
  -- Convert from a stream to the Float value
  streamToFloat :: Stream -> Float
  streamToFloat x =  f x (1)
  
  f :: Stream -> Integer -> Float
  f [] n = 0
  f (y:ys) n = (fromIntegral)y/(fromIntegral(2^n)) + f ys (n+1)
  
  
  
  
  
  -- Add two stream
  addStream :: Stream -> Stream -> Stream
  addStream (x1:x2:x3:xs) (y1:y2:y3:ys) = (u+c):(addStream (x2:x3:xs) (y2:y3:ys))
                                  where u = interim x1 x2 y1 y2
                                        c = carry x2 x3 y2 y3
  
  
  
  -- Compute carry, the C(i) value, given x(i) and y(i)
  carry :: Digit -> Digit -> Digit -> Digit -> Digit
  carry x1 x2 y1 y2
          |t>1                    =  1
          |t<(-1)                 = -1
          |t==1 && (minus1 x2 y2) =  0
          |t==1 && not (minus1 x2 y2) = 1
          |t==(-1) && (minus1 x2 y2) = -1
          |t==(-1) && not (minus1 x2 y2) = 0
          |t==0                           = 0
          where t = x1+y1
  
  
  
  -- Computer the interim sum, the U(i) value, given x(i), y(i) and c(i)
  interim :: Digit -> Digit -> Digit -> Digit -> Digit
  interim x1 x2 y1 y2
                  |t>1                    =  0
                  |t<(-1)                 = 0
                  |t==1 && (minus1 x2 y2) =  1
                  |t==1 && not (minus1 x2 y2) = -1
                  |t==(-1) && (minus1 x2 y2) = 1
                  |t==(-1) && not (minus1 x2 y2) = -1
                  |t==0                           = 0
                  where t = x1+y1
  
  
  
  -- Check if at least one of 2 digits is -1
  minus1 :: Digit -> Digit -> Bool
  minus1 x y = (x==(-1))|| (y==(-1))
  
  
  
  
  
  
  -- Algin two stream so that they have the same length
  align :: Stream -> Stream -> (Stream, Stream)
  align xs ys
          |x>y            = (xs, (copy 0 (x-y)) ++ys)
          |otherwise      = ((copy 0 (y-x)) ++ xs, ys)
          where x = toInteger(length xs)
                y = toInteger(length ys)
  
  
  
  -- Generate a list of x
  copy :: Integer -> Integer -> [Integer]
  copy x n = [x| i<- [1..n]]
  
  
  
  
  
  
  
  -- Add two finite stream (to add the integral part)
  addFiniteStream :: Stream -> Stream -> Stream
  addFiniteStream xs ys = add' u v
                          where (u,v) = align xs ys
  
  
  
  -- Utility function for addFinitieStream
  add' :: Stream -> Stream -> Stream
  add' u v = normalise (f u v)
         where f [] [] = []
               f (x:xs) (y:ys) = (x+y):f xs ys
  
  
  -- Normalise the sum
  normalise :: Stream -> Stream
  normalise = foldr f [0]
              where f x (y:ys) = (u:v:ys)
                                where u = (x+y) `div` 2
                                      v = (x+y) `mod` 2
  
  
  -- Negate a stream
  negate' :: Stream -> Stream
  negate' = map (*(-1))
  
  
  
  -- Compute average of two stream
  -- Using [-2,-1,0,1,2] to add, and then divide by 2
  average :: Stream -> Stream -> Stream
  average xs ys = div2 (add xs ys)
  
  
  -- Addition of two streams, using [-2,-1,0,1,2]
  add :: Stream -> Stream -> Stream
  add (x:xs) (y:ys) = (x+y):(add xs ys)
  
  
  -- Then divided by 2, [-2,-1,0,1,2] -> [-1,0,1]
  div2 :: Stream -> Stream
  div2 (2:xs)             = 1:div2 xs
  div2 ((-2):xs)          = (-1):div2 xs
  div2 (0:xs)             = 0:div2 xs
  div2 (1:(-2):xs)        = div2 (0:0:xs)
  div2 (1:(-1):xs)        = div2 (0:1:xs)
  div2 (1:0:xs)           = div2 (0:2:xs)
  div2 (1:1:xs)           = div2 (2:(-1):xs)
  div2 (1:2:xs)           = div2 (2:0:xs)
  div2 ((-1):(-2):xs)     = div2 ((-2):0:xs)
  div2 ((-1):(-1):xs)     = div2 ((-2):1:xs)
  div2 ((-1):0:xs)        = div2 (0:(-2):xs)
  div2 ((-1):1:xs)        = div2 (0:(-1):xs)
  div2 ((-1):2:xs)        = div2 (0:0:xs)
  
  
  
  test = take 100 (average (rationalToStream (1%2)) (rationalToStream (1%3)))
  