Stream.hs

Stream.hs

{-# OPTIONS_GHC -Wno-x-partial #-}
import Prelude hiding (repeat, map, zipWith, (^))
import qualified Prelude

-- The Stream type
type List   a = [a]
type Stream a = [a]

-- Combinators and Instances defined in the handouts

repeat :: a -> Stream a
repeat x = x : repeat x

map :: (a -> b) -> Stream a -> Stream b
map f xs = f (head xs) : map f (tail xs)

zipWith :: (a -> b -> c) -> Stream a -> Stream b -> Stream c
zipWith f xs ys = f (head xs) (head ys) : zipWith f (tail xs) (tail ys)

--- natural numbers
--- nats = 0 : 1 : 2 : 3 : ......

nats :: Stream Int
nats = undefined


instance Num a => Num (Stream a) where
  (+) = zipWith (+)
  (-) = zipWith (-)
  (*) = zipWith (*)
  negate = map negate
  abs = map abs
  signum = map signum
  fromInteger n = repeat (fromInteger n)


-- squares = 0 : 1 : 4 : 9 : 16 : ...

squares = undefined

-- signs = 1 : (-1) : 1 : (-1) : ...

signs = undefined

-- factorials
-- facts = 1 : (1 * 1) : (2 * 1 * 1) : (3 * 2 * 1 * 1) : (4 * 3 * 2 * 1 * 1) : ..
--      = 1 : 1 : 2 : 6 : 24 : 120 : 720 ...
-- factorial 0     = 1
-- factorial (1+n) = (1+n) * factorial n
-- facts = map factorial nats

facts = undefined

-- multiples of 3
-- mul3 = 0 : 3 : 6 : 9 ...

mul3 = undefined

-- natural numbers NOT divisible by 3
-- nd3 = 1 : 2 : 4 : 5 : 7 : 8 : 10 : ....

nd3 = undefined

-- prefixes :: Stream a -> Stream (List a)
-- prefixes nats = [] : [0] : [0,1] : [0,1,2] : [0,1,2,3] : ...

prefixes xs = undefined

-- suffixes :: Stream a -> Stream (Stream a)
-- suffixes nats = (0:1:2:3:4...) : (1:2:3:4...) : (2:3:4:...) : ..

suffixes xs = undefined

-- Fibonacci (of course!)

fib = undefined

--- "interleaving"

infixr 5 \/

(\/) :: Stream a -> Stream a -> Stream a
xs \/ ys = head xs : ys \/ tail xs

-- natural numbers, in binary

bin  = 0 : 1 + 2 * bin  \/ 2 + 2 * bin
bin' = 1 : 2 * bin' \/ 1 + 2 * bin'

-- (reversed) binary representation?
-- bitRep = "" : "1" : "01" : "11" : "001" : "101" : "011" : "111" : ...


bitRep = [] : bitRep'

bitRep' :: Stream String
bitRep' = undefined

-- most significant bit of (tail nats)
-- msb = 1 : 2 : 2 : 4 : 4 : 4 : 4 : 8 : 8 .....

msb = undefined


--
-- Prove nats = bin ?
--   nats = 0 : 1 + nats
--   bin  = 0 : 1 + 2 * bin \/ 2 + 2 * bin

-- Hint: prove that nats = 2 * nats \/ 1 + 2 * nats

from n = n : from (1+n)

--

infixr 8 ^

(^) :: Stream Int -> Stream Int -> Stream Int
xs ^ ys = head xs Prelude.^  head ys : tail xs ^ tail ys