Homework 6 (Laziness, Streams) from CIS 194 Introduction to Haskell (2015 version) http://www.seas.upenn.edu/~cis194/hw/06-laziness.pdf

HW06.hs

{-# OPTIONS_GHC -Wall #-}
{-# LANGUAGE BangPatterns #-}
module HW06 where

import Data.List
import Data.Functor

-- Exercise 1 -----------------------------------------

-- compute nth Fibonacci number
-- naive recursive version - very slow!
fib :: Integer -> Integer
fib 0 = 1
fib 1 = 1
fib n = (fib (n-1)) + (fib (n-2))

-- Interesting in ghci that you can see the list being evaluated
-- piecemeal (lazily)
fibs1 :: [Integer]
fibs1 = map fib [0..]

-- Exercise 2 -----------------------------------------

-- define more efficiently using zipWith and tail
-- 1 1 2 3 5 8 -- fibs2
-- +
-- 1 2 3 5  -- tail fibs 2
-- =
-- 2 3 5 8 13
-- Even fibs2 100 is almost instant, and fibs2 1000 takes about a second in ghci
fibs2 :: [Integer]
fibs2 = 1 : 1 : zipWith (+) fibs2 (tail fibs2)

-- Exercise 3 -----------------------------------------

data Stream a = Cons a (Stream a)

-- Show instance prints the first 20 elements followed by ellipsis
instance Show a => Show (Stream a) where
    show s = "[" ++ intercalate ", " (map show $ take 10 $ streamToList s)
             ++ ",..."

streamToList :: Stream a -> [a]
streamToList (Cons h t) = h : streamToList t

-- Exercise 4 -----------------------------------------

instance Functor Stream where
    fmap f (Cons h t) = Cons (f h) (fmap f t)

-- Would it make sense to make a Monoid instance for Streams? Why
-- or why not? You do not need to answer this question, but it is a good
-- exercise to think about it

-- Monoid requires mappend and mempty
--
-- mempty makes little sense here:
-- Law: mappend mempty x = x
--   this law can't hold here; there is no identity element
--
-- mappend is possible but futile - concatenating two infinite lists
-- is the same as the first list (at least for all practical purposes)

-- Exercise 5 -----------------------------------------

sRepeat :: a -> Stream a
sRepeat x = Cons x (sRepeat x)

-- sIterate (’x’ :) "o" == ["o", "xo", "xxo", "xxxo", "xxxxo", .
sIterate :: (a -> a) -> a -> Stream a
sIterate rule seed = Cons seed (sIterate rule (rule seed))

-- You will want sInterleave to be lazy in its second parameter. This means that
-- you should not deconstruct the second Stream in the function
-- sInterleave (sRepeat 0) (sRepeat 1) == [0, 1, 0, 1, 0, 1, ..
sInterleave :: Stream a -> Stream a -> Stream a
sInterleave (Cons h t) s2 = Cons h (sInterleave s2 t)

sTake :: Int -> Stream a -> [a]
sTake 0 _ = []
sTake n (Cons h t) = h : sTake (n-1) t 

-- Exercise 6 -----------------------------------------

nats :: Stream Integer
nats = sIterate (1+) 0 -- Do nats start at 0 or 1?

-- The ruler function
-- where the nth element in the stream (assuming the first element
-- corresponds to n = 1) is the largest power of 2 which evenly
-- divides n
-- hint: use sInterleave to produce the pattern; no divisibility testing needed

-- when n is odd -> 0
-- 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
-- 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, . . .
--    1     1     1     1     1     1     1     1
--          1           1           1           1
--                      1                       1
--                                              1
-- let s1 = sInterleave (sRepeat 0) (sRepeat 1) 
-- [0, 1, 0, 1, 0, 1, 0, 1, 0, 1,...
-- let s2 = sInterleave (sRepeat 0) s1
-- [0, 0, 0, 1, 0, 0, 0, 1, 0, 0,...
-- let s3 = sInterleave (sRepeat 0) s2
-- [0, 0, 0, 0, 0, 0, 0, 1, 0, 0,...
-- sum of s1,s2,s3 = 
-- [0, 1, 0, 2, 0, 1, 0, 3, 0, 1...]

-- TODO create a stream of streams? But how to we sum the (infinite) set of elements?
-- could use take, since we only need n elements. Or add a new interleave stream for each
-- value we produce?

-- simple solution follows different lines :-(
ruler :: Stream Integer
ruler = go 0
  where go n = sInterleave (sRepeat n) (go $ n + 1)


-- Exercise 7 -----------------------------------------

-- | Implementation of C rand
-- linear congruential generator
-- Rn = (1103515245 x Rn-1 + 12345) mod 2147483648

rand :: Int -> Stream Int
rand seed = sIterate rule seed where
	rule r = (1103515245 * r + 12345) `mod` 2147483648

-- Exercise 8 -----------------------------------------

-- Just (1096,2147482927)

{- Total Memory in use: 237 MB -}
minMaxSlow :: [Int] -> Maybe (Int, Int)
minMaxSlow [] = Nothing   -- no min or max if there are no elements
minMaxSlow xs = Just (minimum xs, maximum xs)

-- Exercise 9 -----------------------------------------

{- Total Memory in use: 1 MB -}  -- 423 without Bang, 1 with bangs on oldmin,oldmax
minMax :: [Int] -> Maybe (Int, Int)
minMax [] = Nothing
minMax xs = Just $ go xs (maxBound :: Int, minBound :: Int) where
	go [] m = m
	go (x:t) (!oldmin, !oldmax) = go t (newmin, newmax) where
		newmax = maximum [x, oldmax]
		newmin = minimum [x, oldmin]

main :: IO ()
main = print $ minMax $ sTake 1000000 $ rand 7666532

-- Exercise 10 ----------------------------------------

fastFib :: Int -> Integer
fastFib 0 = 1
fastFib n = case (M 1 1 1 0) ^ n of (M x _ _ _ ) -> x

-- 2x2 matrix of Integers
-- 00 10
-- 01 11
data Matrix = M Integer Integer Integer Integer -- 00, 01, 10, 11

instance Num Matrix where
	(*) (M x00 x01 x10 x11) (M y00 y01 y10 y11) = 
		   M (x00 * y00 + x10 * y01) (x00 * y10 + x10 * y11) (x01 *y00 + x11 * y01) (x01 * y10 + x11 * y11) 

instance Show Matrix where
    show (M x00 x01 x10 x11) = "[ " ++ (show x00) ++ " " ++ (show x10) ++ " ]\n[ " ++ (show x01) ++ " " ++ (show x11) ++ " ]"