CPSC 370: Functional and Logic Programming ( Fall 2013)

2013-09-06

1. How many partial functions are there from { Scissors, Paper, Rock, Spock, Lizard } ² 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.

2013-09-15

3. What does the function

   fun q f a b = f(a,b) ;
           

   do? What is its type?

2013-09-18

4. Write a Standard ML function uncurry3 that takes a twice-Curried (“three argument”) function and returns an ordinary ternary (three argument) function.

2013-09-22

6. 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).

7. Using the relations
   
   write a Scheme program to calculate e to the x. Compare your results with the builtin exp function.

   (Note that , or .)

2013-09-27

The following questions ask you to code various Standard ML list functions. Please code your solutions from scratch.

8. Write the concat function that takes a list of lists to a list. By example,
   concat [[3,1,2],[],[],[3],[1]] is
   [3,1,2,3,1]. For this question, you may use the builtin function @, which appends one list to another.
9. Write the exists function that takes a predicate (a function whose return type is bool) and (curried) a list and returns true or false depending on whether any element of the list satisfies the predicate.
10. Write the all function that works like any, except that it returns true or false depending on whether all elements of the list satisfy the predicate.
11. Write the tabulate function. This is a two‐argument function whose first argument is an integer that equals the length of the list returned, and whose second argument is a function. This latter function takes a zero-indexed position, and returns the corresponding element of the answer.

    Example

    tabulate (3,Int.toString)
    returns
    ["0","1","2"]

---

12. Write the take function in Scheme.

2013-10-09

13. Re-solve Question 11 (tabulate in in Standard ML) in a tail-recursive way.

2013-10-21

14. Draw syntax diagrams for Standard ML record patterns and Standard ML record types similar to the syntax diagram for record values given in the handout.

2013-10-27

14. Consider the code for persistent arrays handed out in class (see also here.)
15. Show how to extend persistent arrays to have the following functions:
    1. val exists: α array → bool which works analogously to all
    2. val take: int × α array → α array which works similarly to drop, but returns the first n elements.
    3. val map: (α → β) → (α array → β array) which applies a given function to every element of a given persistent array. Estimate the time complexity of your map function.
16. Rewrite rev to be tail-recursive.

2013-11-06

17. Determine what the combinator S(S(KS)(S(KK)S))(KK) does.

    Hint: The easiest way to unravel this is to un-apply η-reduction. That is, replace
    S(S(KS)(S(KK)S))(KK) with
    λ f.S(S(KS)(S(KK)S))(KK)(f), apply the combinator rules that you can. Then apply this trick again a couple of times to the body of the simplified
    λ f.S(S(KS)(S(KK)S))(KK)(f) expression.

    If you have done things correctly, you should end up with short λ-expression of three variables.

18. Translate λNfx.Nf(fx) into an SKI combinator.

2013-11-10

19. Write a Standard ML function that computes all of the k element sub-lists of a given list. For instance sublists(3,[1,2,3,4,5]) should produce

    [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5],
     [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]
            

20. One approach to the problem above is to first list the sublists that involve the first element, then those that don’t. The structure is shown below.

    > >

    Structure of the sublist problem

    1	sublist(2,[2,3,4,5])
    sublist(3,[2,3,4,5])

    This suggest code of the form
    (map ??? recursive_call) @ (recursive_call)
    

    An inefficiency here is that the first list gets generated first by the recursive call, then again, by the map function, then a third time by the append.

    We can remove the need for the map call by generalizing sublist.
    Define sublistB f (k, list)
    to produce the same thing as map f (sublist (k, list)) , but do so in a way that sublistB calls itself and does not call map.

    Using a let-block, code sublist so that sublist (k, list) calls sublistB I (k, list).

21. We are now in a position to generalize further to avoid the repeated append.

    Define sublistC f (k, list) acc
    to produce the same thing as sublistB f (k, list) @ acc, but do so in a way that sublistC calls itself.

2013-11-23

22. Write a Prolog predicate sublist(?Small,+K,?Big) that holds when Small is a K element sublist of Big.

2013-11-24

23. Write Prolog predicates portrayAppLeft and portrayAppRight so that λ-terms display nicely.
24. Recall that η-reduction is the process of converting λx.F(x) to F. Note that η-reduction is only valid when F itself is free of the variable x. Write a Prolog predicate etaReduces(+A,-B) that succeeds when B is the η-reduction of A, where A and B are coded as in class.
25. Write a Prolog predicate to convert that involves λ-terms to one that consists solely of S, K, and I combinators.

    Here is a sketch of a strategy:

    • A(B) converts to A′(B′) where A converts to A′ and B converts to B′.
    • Unbound variables stay unchanged.
    • λx.C converts to KC′ where C converts to C′, provided that C is free of x.
    • λx.x converts to I.
    • λx.A(B) converts to S(A′)(B′) where λx.A converts to A′ and λx.B converts to B′.

    (Caution: when removing λs you may need to lower the index in bound variables. For instance when converting λxyz.x (aka λλλ.2), you recursively encounter the problem λ.2, which should translate to K1, not K2.)

    Try this on the μ (Y) combinator, where the μ combinator is given by λGx.[λy.yy] (λRz.G(RR)z)x.