This is a course page of David Casperson 

… can be found
under Assigned…
(http://web.unbc.ca/Semesters/201705F/370homeworkpending.php
)
Bonus: How many of these are fair and interesting?
1
.
(require rackunit)
.
F_{0} = 0; F_{1} = 1; F_{n} = F_{n1} + F_{n2} .
Program this in Racket and Haskell.
F_{0} = 0;
F_{n} =
(F_{n1} +
G_{n1}) / 2;
G_{0} = 2;
G_{n} =
(5 × F_{n1} +
G_{n1}) / 2;
.
Program this in Racket and Haskell by writing functions that return the (F_{n}, G_{n}) pair as a function of n.
Comment on how fast or slow this is.
F_{2n} =
F_{n} ×
G_{n} ;
G_{2n} =
(5 × F_{n}^{2} +
G_{n}^{2}) / 2;
.
Write a Program to compute Fibonacci numbers in Racket and in Haskell that use this relation for nonzero even arguments, and the code from the previous part otherwise.
Comment on how fast or slow this is.
Y
(from the days
when everything was ASCII) or μ
(by analogy with
λ).
In Haskell
functions need to be lower case so it is convenient to use
μ
or
mu
.
It is defined by
μ ff x = ff (μ ff) xDetermine the type of μ by reasoning from its definition. Verify your answer using
ghci
.
(What do you think μ
is good for?)
fib fib n = if n<2 then n else fib (n1) + fib (n2)in place of
fib n = if n<2 then n else fib (n1) + fib (n2)
fib ff n = if n<2 then n else ff (n1) + ff (n2)
fib
function?
Why?
fib ff n = if n<(2::Int) then (fromIntegral n)::Integer else ff (n1) + ff (n2)to force some of the numeric types, what is the type of this
fib
function?
fib
recursively defined?undefined
fib undefined
fib . fib $ undefined
fib . fib . fib $ undefined
(fib undefined) 1
(fib undefined) 2
(fib . fib $ undefined) 2
(fib . fib $ undefined) 3
(fib . fib . fib $ undefined) 3
μ
and fib
functions from the
preceding two questions, what is the value of μ fib
10
?
Explain what is going on.