Last modified: 2021-05-21
This is a course page of
David Casperson
Associate Professor
Computer Science
University of Northern British Columbia

CPSC 370: Functional and Logic Programming (2011)

Homework Questions now Due

Due Friday, October 7, 2011.

Pressman’s instructions) For more details go here.
  • This question is about sorting and related ideas.
    1. Determine what the order datatype is. Explain how
       type α comparator 
        = α * α -> order ; 
      corresponds to the Java concept of Comparable.
    2. Write a function isSortedwith signature α comparator -> α list -> bool. Test it. (You may wish to note that there are builtin functions and that have the types int comparator and string comparator respectively.)
    3. Write a function insertwith signature α comparator -> α * α list -> α list that inserts an item into a sorted list. Test it.
    4. Write a function insertionSortwith signature α comparator -> α list -> α list that insertion sorts a list. Test it. Re-code this beautifully in one line.

  • Write a function that counts the number of correct colours in incorrect places (the number of white pegs in the 1970's Mastermind game. See also Pressman’s instructions)

  • Due Wednesday, November 02.

    1. Given
              datatype α tree 
                   = E | T of ( α tree * α * α tree )
      write a tail-recursive function that sums the values of an int tree.
    2. Given
              datatype choice 
                  = Rock | Paper | Scissors 
                  | Spock | Lizard ;
              datatype result = win | lose ;
      write something like a partial function from choice * choice to result that plays “rock paper scissors Spock lizard” correctly. Rules of RPSSL

      Maximum points for cutely coded solutions.

    Due Monday, November 07.

    1. Unicode unifies most of world’s characters by giving each character a code between 0 and 2097151 (221-1), the first 128 of which are identical to ASCII.

      UTF-8 is a way to convert a series of Unicode codes to bytes. There is a nice FAQ describing UTF-8 and Unicode.

      1. Write a function to convert a list of Unicode values into a corresponding UTF-8 values.
      2. Combine the above with CharVector.fromList and Char.chr to get a function that converts an int list of Unicode codes to a CharVector.vector (aka a string).
      3. Use the TextIO.openOut, TextIO.output, and TextIO.closeOut functions to write appropriate test strings to a text file. Try displaying the resulting file on a UNIX machine.
    2. Scheme Homework.
    3. Using the relations
      Equations for e to the x
      write a Scheme program to calculate e to the x. Compare your results with the builtin exp function.

      Note that Equation for sum.

    4. Look up the definition of the flatten function, and write and test your own definition.
    5. Look up the definitions of the special forms (and …) and (or …). Explain why these are syntactic sugar for other Scheme forms.


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

    2. Write a Prolog predicate constant/1 that unifies with mathematically constant expressions, that is: numbers; sums, products, and so on, of constants; special constants like pi and e; and functions applied to constants. (You may wish to look at the functor/3 and arg/3 builtin predicates.)
    3. Write a prolog predicate deriv/3 with argument pattern deriv(+Term,+MathVar,-Result) that applies standard first-year calculus derivation rules. The predicate should support application of the chain rule.
    Home page Semesters Site Map
    go back Fall 2011 go forward
    2023-10 other links

    CPSC 100 [Other years]
    CPSC 370 [Other years]
    Prolog resources
    Blackboard Link
    David’s Schedule