CPSC 370: Functional and Logic Programming (
Fall 2017)
Questions Still Pending
… can be found
under Assigned…
(http://web.unbc.ca/Semesters/2017F/370homeworkpending.php )
Questions Due Monday, November 06.
Assigned 20170911

Give two examples of Java syntactic
sugar.
Assigned 20170929

How many partial functions are there from
{ Scissors, Paper, Rock, Spock, Lizard } ^{2}
to { Win, Lose } ?
Bonus: How many of these are fair and interesting?

Implement a function that takes a pair of real
numbers m and b and returns the linear
function mx+b.

What is wrong with the wording above?

Implement this in Haskell.

Implement this in Racket.

Implement this in Java.

A Collatz sequence starts with an arbitrary positive
integer n. The next number in the sequence is
 3n+1 if n is odd, and
 n/2 if n is even.
A sequence ends when n reaches 1 .

Write a Racket program that
repeatedly asks the user for a starting number and then
displays the resulting Collatz sequence.

Add a way for the user to terminate the program.
 Write a similar program
in Haskell.

Add test functions to the Racket
code by using
(require rackunit)
.
Questions Due Wednesday, November 08.
Assigned 201710??

Here are several ways to compute the Fibonacci numbers.

The
standard definition is
F_{0} = 0;
F_{1} = 1;
F_{n} =
F_{n1} +
F_{n2} .
Program this in
Racket
and
Haskell.

The running time for this definition is exponential.
Determine for what n
(Racket
and
Haskell),
you can go get coffee in the time it takes the function to
compute F_{n}.

A different definition of the Fibonacci numbers is given by
F_{0} = 0;
F_{n} =
(F_{n1} +
G_{n1}) / 2;
G_{0} = 2;
G_{n} =
(5 × F_{n1} +
G_{n1}) / 2;
.
(Here the F_{n} are the Fibonacci
number, the G_{n} are just helpers.
In fact, G_{n} = 2 ×F_{n1} + F_{n}.)
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.

Another set of equations which make for faster recursion are:
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.

This question and the following two questions
introduce a theoretically important function, and gradually
explores its properties.
The function is variously called
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) x
Determine the type of μ by reasoning from its definition.
Verify your answer using ghci .
(What do you think μ is good for?)

Consider what happens when you “stutter” while
defining a recursive function, for instance writing
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)
 Explain why the former is equivalent to
fib ff n = if n<2 then n else ff (n1) + ff (n2)
 What is the type of this
fib function?
Why?
 Using
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?
 Is this version of
fib recursively defined?

What are the types of the following sequence of expressions?
undefined
fib undefined
fib . fib $ undefined
fib . fib . fib $ undefined
 …

What are the values of the following expressions?
(fib undefined) 1
(fib undefined) 2
(fib . fib $ undefined) 2
(fib . fib $ undefined) 3
(fib . fib . fib $ undefined) 3
What is the general rule?

Using the
μ and fib functions from the
preceding two questions, what is the value of μ fib
10 ?
Explain what is going on.
