1 {-# OPTIONS_GHC -Wall #-}
2 {-# OPTIONS_GHC -fno-warn-missing-methods #-}
3 {-# LANGUAGE InstanceSigs #-}
4 {-# LANGUAGE FlexibleInstances #-}
8 fib :: Integer -> Integer
11 fib n = fib (n - 1) + fib (n - 2)
16 -- exercise 2: define a more efficient fibs
19 where fs = zipWith (+) fibs2 (tail fibs2)
21 -- exercise 3 -- streams
22 data Stream a = Cons a (Stream a)
24 -- stream to infinite list
25 streamToList :: Stream a -> [a]
26 streamToList (Cons x sx) = x : streamToList sx
28 -- instance of Show for Stream
29 instance Show a => Show (Stream a) where
30 show :: Stream a -> String
31 show sx = init (tail (show (take 20 (streamToList sx)))) ++ "..."
33 -- exercise 4 - stream repeat
34 streamRepeat :: a -> Stream a
35 streamRepeat x = Cons x (streamRepeat x)
38 streamMap :: (a -> b) -> Stream a -> Stream b
39 streamMap f (Cons x xs) = Cons (f x) (streamMap f xs)
42 streamFromSeed :: (a -> a) -> a -> Stream a
43 streamFromSeed f x = Cons x (streamFromSeed f (f x))
45 -- exercise 5: define a few streams
48 nats :: Stream Integer
49 nats = streamFromSeed (+1) 0
55 ruler :: Stream Integer
57 which corresponds to the ruler function
58 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, . . .
60 where the nth element in the stream (assuming the first element
61 corresponds to n = 1) is the largest power of 2 which evenly
65 interleaveStreams :: Stream a -> Stream a -> Stream a
66 interleaveStreams (Cons x xs) ys = (Cons x (interleaveStreams ys xs))
68 ruler :: Stream Integer
69 ruler = interleaveStreams (streamRepeat 0) (foldr interleaveStreams (streamRepeat 0) (map streamRepeat [1..]))
71 -- fibonacci numbers via generating functions
74 -- define x :: Stream Integer
75 -- x = 0 + 1.x + 0.x^2 + 0.x^3 + 0.x^4 + ...
77 x' = Cons 0 (Cons 1 (streamRepeat 0))
79 -- implement an instance of Num type class for Stream Integer
80 instance Num (Stream Integer) where
81 fromInteger :: Integer -> Stream Integer
82 fromInteger n = Cons n (streamRepeat 0)
83 negate :: Stream Integer -> Stream Integer
84 negate sx = streamMap (* (-1)) sx
85 (+) :: Stream Integer -> Stream Integer -> Stream Integer
86 (+) (Cons x sx) (Cons y sy) = (Cons (x+y) ((+) sx sy))
87 (*) :: Stream Integer -> Stream Integer -> Stream Integer
88 (*) (Cons x sx) (Cons y sy) = Cons (x*y) ((streamMap (* x) sy) + sx*(Cons x sx))