CIS194 Homework 6: http://www.seas.upenn.edu/~cis194/lectures.html

hw6.hs

-- http://www.seas.upenn.edu/~cis194/hw/06-laziness.pdf
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE InstanceSigs #-}
{-# OPTIONS_GHC -fno-warn-missing-methods #-}

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

fibs1 :: [Integer]
fibs1 = map fib [0..]

fibs2 :: [Integer]
fibs2 = map fst $ iterate next f0 where
  f0 = (0, 1)
  next (a, b) = (b, a + b)

data Stream a = Stream a (Stream a)

streamToList :: Stream a -> [a]
streamToList (Stream a as) = a : streamToList as

instance Show a => Show (Stream a) where
  show s = show . take 40 . streamToList $ s

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

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

streamFromSeed :: (a -> a) -> a -> Stream a
streamFromSeed f x = Stream (f x) (streamFromSeed f (f x))

nats :: Stream Integer
nats = streamFromSeed (+1) 0

interleaveStreams :: Stream a -> Stream a -> Stream a
interleaveStreams (Stream x xs) ys = Stream x (interleaveStreams ys xs)

ruler :: Stream Integer
ruler = rulerCore 0 where
  rulerCore x = interleaveStreams (streamRepeat x) (rulerCore (x + 1))

x :: Stream Integer
x = Stream 0 $ Stream 1 $ streamRepeat 0

instance Num (Stream Integer) where
  fromInteger :: Integer -> Stream Integer
  fromInteger n = Stream n (streamRepeat 0)

  negate :: Stream Integer -> Stream Integer
  negate ns = streamMap negate ns

  (+) :: Stream Integer -> Stream Integer -> Stream Integer
  (+) (Stream x xs) (Stream y ys) = Stream (x + y) (xs + ys)

  (*) :: Stream Integer -> Stream Integer -> Stream Integer
  (*) (Stream x xs') ys @ (Stream y ys') = Stream (x * y) $ (streamMap (* x) ys') + (xs' * ys)

instance Fractional (Stream Integer) where
  (/) :: Stream Integer -> Stream Integer -> Stream Integer
  (/) (Stream x xs) (Stream y ys) = q where
    q = Stream (x `div` y) $ streamMap (`div` y) $ (xs - q * ys)

fibs3 :: Stream Integer
fibs3 = x / (1 - x - x^2)