CPSC 370: Functional and Logic Programming ( Fall 2017)

Assigned 2017-09-11

1. Give two examples of Java syntactic sugar.

Assigned 2017-09-29

2. How many partial functions are there from { Scissors, Paper, Rock, Spock, Lizard } ² to { Win, Lose } ?

   Bonus: How many of these are fair and interesting?

3. 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.

4. Write a Racket program that repeatedly asks the user for a starting number and then displays the resulting Collatz sequence.
5. Add a way for the user to terminate the program.
6. Write a similar program in Haskell.
7. Add test functions to the Racket code by using (require rackunit) .

Assigned 2017-10-??

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

      F₀ = 0;   F₁ = 1;   F_n = F_n-1 + F_n-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 F_n.
   3. A different definition of the Fibonacci numbers is given by

      F₀ = 0;   F_n = (F_n-1 + G_n-1) / 2;
      G₀ = 2;   G_n = (5 × F_n-1 + G_n-1) / 2; .

      (Here the F_n are the Fibonacci number, the G_n are just helpers. In fact, G_n = 2 ×F_n-1 + 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.

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

      F_2n = F_n × G_n ;
      G_2n = (5 × F_n² + G_n²) / 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.

9. 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?)
10. 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?
11. Using the μ and fib functions from the preceding two questions, what is the value of μ fib 10? Explain what is going on.