Last modified: 2023-11-14
This is a course page of
David Casperson
Associate Professor
Computer Science
University of Northern British Columbia

CPSC 370: Functional and Logic Programming (2012)

Homework Questions due Wednesday December 5, 2012

  1. Translate SK into a pure λ-term.
  2. Translate λNfx.Nf(fx) into an SKI combinator.
  1. Write Prolog rules for a predicate nth so that nth(2,[a,b,c,d],c). returns true.

    Make your rules cope with as many situations as possible. For instance, it would be nice if your rules find both N=0 and N=2 when given the query. nth(N,[a,b,a,d],a). Comment on the combinations of variables that rules handle.

    N.B., this is builtin as predicate nth0, and there are answers on StackOverflow and elsewhere for how to do this. Write your own! (first.)

  2. The goal of this question is to do arithmetic on natural numbers (0,1,2,…) without using the Prolog predicates such as is. To do this represent the natural numbers as zero, s(zero), s(s(zero)), ….

    1. Write a predicate isNat(X) that is true for zero, s(zero), s(s(zero)), …, and no other ground terms..
    2. Write a predicate xTo(?N, ?X) that converts between non-negative integers and isNat numbers.
    3. Using portray, cause Prolog to print s(s(zero)) as N(2), and so on.
    4. Write a predicate xPlus(?X,?Y,?Z) that succeeds when at least two of X, Y, and Z are ground and a solution is possible [ xPlus(X,s(zero),zero) should fail]. The idea that you want to exploit is
      s(X)+Y=s(Z)   iff X+Y=Z.
    5. Write a predicate xTimes(?X,?Y,?Z) that succeeds when at least two of X, Y, and Z are ground and a solution is possible.
    6. Write a predicate xLessEq(?X,?Y) that succeeds when XY.
    7. Write a predicate xQuoRem(+X,+Y,-Z,-W) that succeeds when X=0 or Y>0. Solutions should satisfy xLessEq(s(W),Y),xTimes(Z,Y,X1),xPlus(X1,W,X).


Previously due Wednesday, October 31, 2012.

  1. Write an integer gcd function.
  2. Write an integer lcm function.
  3. Consider α trees defined by the datatype
    datatype α tree = Empty | Node of α tree * α * α tree ;

    Write a function that takes an integer n and produces a nearly balanced tree whose nodes in-order are the integers 1 through n.

  4. Write a function that takes an α list and produces a nearly balanced α tree whose node values are taken from the list.
  5. Given that tree folding is defined by
    fun fold (f:β * α * β → β) (b:β) (Empty:α tree) : β = b
       | fold (f:β * α * β → β) (b:β) (Node (l,n,r)) = f(fold f l, n, fold f r)

    write functions that compute
    1. depth
    2. total node count
    3. postorder:α tree → α list, that gives a list of the nodes in post-order.
    using fold.
  6. Write a tail recursive version of fold that uses continuations to achieve tail-recursiveness.
  7. Consider α queues defined by the datatype
    datatype α queue = Q of α list * α list ;
    as discussed in class.

    Implement the functions

    snoc   : α * α queue -> α queue ;
    pop    : α queue -> (α * α queue) option
    isEmpty: α queue -> bool
          
    where
    snoc
    adds an element to the tail of a queue
    pop
    removes the front element from a queue, return a pair consisting of the front element and the remainder of the queue. Returns NONE if the queue is empty.
    isEmpty
    Self explanatory.


Previously due Friday, September 28, 2012.

  1. Give an example of syntactic sugar in Java.
  2. How many partial functions are there from { Scissors, Paper, Rock, Spock, Lizard } 2 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.
  4. Implement a function that takes a triple of real numbers (a,b,c) and computes the roots r1 and r2 of the quadratic equation 0 = ax2 + bx + c .

    To do this, find the larger root (in absolute value) using the quadratic formula. Find the smaller root using the fact that a r1 r2 = c.

    • Implement this in Standard ML.
    • Implement this in Scheme.
  5. Here is a question about Standard ML syntax.
    • Is it possible to have “let let” in a legal Standard ML program (other than silly ways, such as in a string constant)?
    • Is it possible to have “local local” in a legal Standard ML program (other than silly ways, such as in a string constant)?
    In each case, either give an example showing that it is possible, or give a reasoned argument as to why it is impossible.

Home page Semesters Site Map
go back Fall 2012 go forward
2024-12 other links

CPSC 100 [Other years]
CPSC 370 [Other years]
Books
Homework
Dates
Policies
Prolog resources
Blackboard Link
Java
David’s Schedule

fall-2024