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/2017F/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 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.
  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.
Home page Semesters Site Map
go back Fall 2017 go forward
2017-11 other links

CPSC 370 [Other years]
References
Homework
Dates
Policies
Resources
David’s Schedule

UNBC Undergraduate Calendar