This is a course page of
David Casperson
 Associate Professor Computer Science University of Northern British Columbia

# CPSC 370: Functional and Logic Programming ( Fall 2017)

## Questions Still Pending

… can be found under Assigned… (`http://web.unbc.ca/Semesters/2017-05F/370-homework-pending.php`)

## Questions Due Monday, November 06.

1. Give two examples of Java syntactic sugar.
1. 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?

2. 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 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`.
1. Write a Racket program that repeatedly asks the user for a starting number and then displays the resulting Collatz sequence.
2. Add a way for the user to terminate the program.
3. Write a similar program in Haskell.
4. Add test functions to the Racket code by using ``` (require rackunit) ```.

## Questions Due Wednesday, November 08.

1. Here are several ways to compute the Fibonacci numbers.
1. The standard definition is

F0 = 0;   F1 = 1;   Fn = Fn-1 + Fn-2 .

Program this in Racket and Haskell.
2. 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 Fn.
3. A different definition of the Fibonacci numbers is given by

F0 = 0;   Fn = (Fn-1 + Gn-1) / 2;
G0 = 2;   Gn = (5 × Fn-1 + Gn-1) / 2; .

(Here the Fn are the Fibonacci number, the Gn are just helpers. In fact, Gn = 2 ×Fn-1 + Fn.)

Program this in Racket and Haskell by writing functions that return the (Fn, Gn) pair as a function of n.

Comment on how fast or slow this is.

4. Another set of equations which make for faster recursion are:

F2n = Fn × Gn ;
G2n = (5 × Fn2 + Gn2) / 2; .

Write a Program to compute Fibonacci numbers in Racket and in Haskell that use this relation for non-zero even arguments, and the code from the previous part otherwise.

Comment on how fast or slow this is.

2. 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?)
3. Consider what happens when you “stutter” while defining a recursive function, for instance writing
```  fib fib n = if n<2 then n else fib (n-1) + fib (n-2)
```
in place of
```  fib n = if n<2 then n else fib (n-1) + fib (n-2)
```
1. Explain why the former is equivalent to
```  fib ff n = if n<2 then n else ff (n-1) + ff (n-2)
```
2. What is the type of this `fib` function? Why?
3. Using
```  fib ff n = if n<(2::Int)
then (fromIntegral n)::Integer
else ff (n-1) + ff (n-2)
```
to force some of the numeric types, what is the type of this `fib` function?
4. Is this version of `fib` recursively defined?
5. What are the types of the following sequence of expressions?
• `undefined`
• `fib undefined`
• `fib . fib \$ undefined`
• `fib . fib . fib \$ undefined`
6. 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?
4. Using the `μ` and `fib` functions from the preceding two questions, what is the value of ```μ fib 10```? Explain what is going on.
 Fall 2017 2022-12

CPSC 370
References
Lecture Planning
Homework
Dates
Policies
Resources
David’s Schedule