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

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

## Questions Still Pending

can be found here .

## Due 2015-09-21

1. Read Chapter 2 of Learn You a Haskell for Great Good. Then send me an e-mail message explaining what you understand to be the differences between lists and tuples.

## Due 2015-09-28

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

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 Standard ML.
• Implement this in Scheme.
• Implement this in Java.

## Due 2015-10-09

1. Give examples of syntactic sugar (the more obscure the better) in Java, Haskell, and Scheme.

1. Write an `init` function in Scheme.

## Due 2015-11-04

1. Write a Haskell function `uncurry` that takes a function of type ` a → b → c ` and returns a function of type ` (a,b) → c `.
2. Write a Scheme function `curry` that takes a two argument function and returns its Curried equivalent.
3. Find out what `and` and `or` do in Scheme (or Racket).
• Explain why neither can be implemented as functions.
• Explain how they can be viewed as syntactic sugar.
4. Write a Scheme function to compute the roots of the quadratic polynomial a x 2 + b x + c = 0. Use the facts that
• When (b2 − 4 a c) < 0, there are no real roots.
• When (b2 − 4 a c) = 0, there is one (repeated) root.
• Changing the sign of b changes the sign of the roots, but does not change their magnitude.
• When b < 0, the larger root (in absolute magnitude) is given by ( √ (b2 − 4 a c) − b)/ (2a) and has the same sign as a.
• a times the product of the roots is c, which is a numerically accurate way to compute the smaller root (in absolute magnitude).
1. Write a Scheme function that contains one `let`-style block that returns three different answer depending on whether one uses “`let`”, “`let*`”, or “`letrec`”.
2. Write a Haskell tail-recursive function that counts the number of leaves in a

``` data Tree a = Leaf a | Branch (Tree a) (Tree a) ```

tree by using continuations.

Repeat using another strategy to make the function tail-recursive.

## Due 2015-11-06

1. Write a Haskell tail-recursive function that makes an in-order list of the leaf values in a

``` data Tree a = Leaf a | Branch (Tree a) (Tree a) ```

tree by using continuations.

Repeat using another strategy to make the function tail-recursive.

2. Suppose that you have a binary tree where every non-leaf has exactly two branches:

``` data Tree a = Leaf a | Branch (Tree a) (Tree a) ```
1. [Haskell] Write a program that gives a list of non-negative integers corresponding to depths of the leaves, scanned in in-order.

2. [Haskell] Make this program tail-recursive.

3. [Haskell, Scheme] Write a program that given a list of non-negative integers, determines whether or not they could be the outcome of the previous part.

For instance, `[1,2,2]` is a possible output, but `[2,1,2]` is not.

Hint: A more general problem is whether or not an initial segment of the list is the set of heights of a sub-branch sitting at depth k.    Fall 2015 2023-09 CPSC 370
References
Homework
Dates
Policies
Prolog resources
David’s Schedule