hw6/Fibonacci.hs

   1 {-# OPTIONS_GHC -Wall #-}
   2 {-# OPTIONS_GHC -fno-warn-missing-methods #-}
   3 {-# LANGUAGE InstanceSigs #-}
   4 {-# LANGUAGE FlexibleInstances #-}
   5 module Fibonacci where
   6
   7 -- exercise 1
   8 fib :: Integer -> Integer
   9 fib 0 = 0
  10 fib 1 = 1
  11 fib n = fib (n - 1) + fib (n - 2)
  12
  13 fibs1 :: [Integer]
  14 fibs1 = map fib [0..]
  15
  16 -- exercise 2: define a more efficient fibs
  17 fibs2 :: [Integer]
  18 fibs2 = 0 : 1 : fs
  19     where fs = zipWith (+) fibs2 (tail fibs2)
  20
  21 -- exercise 3 -- streams
  22 data Stream a = Cons a (Stream a)
  23
  24 -- stream to infinite list
  25 streamToList :: Stream a -> [a]
  26 streamToList (Cons x sx) = x : streamToList sx
  27
  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)))) ++ "..."
  32
  33 -- exercise 4 - stream repeat
  34 streamRepeat :: a -> Stream a
  35 streamRepeat x = Cons x (streamRepeat x)
  36
  37 -- streamMap
  38 streamMap :: (a -> b) -> Stream a -> Stream b
  39 streamMap f (Cons x xs) = Cons (f x) (streamMap f xs)
  40
  41 -- streamFromSeed
  42 streamFromSeed :: (a -> a) -> a -> Stream a
  43 streamFromSeed f x = Cons x (streamFromSeed f (f x))
  44
  45 -- exercise 5: define a few streams
  46
  47 -- nats
  48 nats :: Stream Integer
  49 nats = streamFromSeed (+1) 0
  50
  51 -- ruler
  52 {- | ruler stream
  53 Define the stream
  54
  55 ruler :: Stream Integer
  56
  57 which corresponds to the ruler function
  58 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, . . .
  59
  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
  62 divides n
  63
  64 -}
  65 interleaveStreams :: Stream a -> Stream a -> Stream a
  66 interleaveStreams (Cons x xs) ys = (Cons x (interleaveStreams ys xs))
  67
  68 ruler :: Stream Integer
  69 ruler = interleaveStreams (streamRepeat 0) (foldr interleaveStreams (streamRepeat 0) (map streamRepeat [1..]))
  70
  71 -- fibonacci numbers via generating functions
  72 -- exercise 6
  73
  74 -- define x :: Stream Integer
  75 -- x = 0 + 1.x + 0.x^2 + 0.x^3 + 0.x^4 + ...
  76 x' :: Stream Integer
  77 x' = Cons 0 (Cons 1 (streamRepeat 0))
  78
  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))