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.

Home page Semesters Site Map
go back Fall 2015 go forward
2023-09 other links

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

UNBC Undergraduate Calendar