CPSC 370: Functional and Logic Programming ( Fall 2015)

---

Questions Still Pending

can be found here .

---

Due 2015-09-21

2015-09-11

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

2015-09-11

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

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

---

Due 2015-10-09

2015-09-22

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

2015-09-30

5. Write an init function in Scheme.

---

Due 2015-11-04

2015-10-05

6. Write a Haskell function uncurry that takes a function of type a → b → c and returns a function of type (a,b) → c .
7. Write a Scheme function curry that takes a two argument function and returns its Curried equivalent.
8. 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.
9. Write a Scheme function to compute the roots of the quadratic polynomial a x ² + b x + c = 0. Use the facts that
   • When (b² − 4 a c) < 0, there are no real roots.
   • When (b² − 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 ( √ (b² − 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).

2015-10-09

10. Write a Scheme function that contains one let-style block that returns three different answer depending on whether one uses “let”, “let*”, or “letrec”.

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

2015-10-29

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

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