-- Carsten Schuermann
-- Lazy streams.

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)


-- Easy lazy streams

ones = 1 : ones
twos = 2 : twos

-- zipWith': A function that combines two streams
-- Invariant: zipWith' f as bs = cs
--      If   as : list T1
--      and  bs : list T2
--      and  f  : T1 -> T2 -> T3
--      then cs : list T3
--      and  cs[i] = f (as[i]) (bs[i])

zipWith' f (a : as) (b : bs) = f a b  : zipWith' f as bs

-- nth': A function that selects the nth element from a stream
-- Invariant: nth' n (a0 : ... : an : t) = an

nth' 0 (h : _) = h
nth' n (_ : t) = nth' (n-1) t

-- take' n s = l
-- Invariant:  |l|= n and s[i] = l[i]

take' 0 s = []
take' n (h : t) = h : take' (n-1) t 

-- Example

l3 = zipWith' (+) ones twos
l4 = zipWith' (*) ones twos 


-- More lazy streams

odd' = 1 : zipWith' (+) odd' twos
even' = zipWith' (-) odd' ones
fib' = 1 : 1 : zipWith' (+) fib' (tail fib')

-- Result:  We can program memoization with lazy streams.