This is a course page of
David Casperson
Associate Professor
Computer Science
University of Northern British Columbia

CPSC 370: Functional and Logic Programming ( Fall 2016)

Questions Still Pending

All homework for CPSC 370 Fall 2016 now has an assigned due date below.

Questions Due Wednesday, December 07

  1. The aim of this question is to write a simple differentiator in Prolog. For the sake of simplicity, assume that all differentiation is being done with respect to the variable x. Handle the following rules Calculus rules
  1. The aim of this question is to learn to write DCG clauses in Prolog. In this question imagine that we are parsing a language where comments are delimented by '{' and '}'.

    Here is a specification by example:

    • parse_comments("{cat}",X). succceeds with X=[comment(["cat"])].
    • parse_comments("{cat}{dog}",X). succceeds with X=[comment(["cat"]), comment(["dog"])].
    • parse_comments("a{cat}house{dog}boat",X). succceeds with X=["a", comment(["cat"]), "house", comment(["dog"]), "boat"].
    • parse_comments("}{cat}",X). fails.

    Only slightly harder, also handle nested comments.

    • parse_comments("{{cat}}",X). succceeds with X=[ comment([ comment(["cat"]) ]) ].
    • parse_comments("{{a}b}c",X). succceeds with X=[ comment([ comment(["a"]), "b"]), "c" ].

    Here is a slightly tangled set of rules

    • A non-comment is a sequence of characters excluding '{' and '}'. A non-comment may be empty. A non-comment is represented by a string.
    • A scan is a sequence of non-comments separated by comments. A scan is represented by a list. Empty non-comments may be dropped from the list.
    • A comment starts with a '{' and ends with a '}'. In between the braces is a scan. A comment is represented by comment() where the dots represent a scan.

    Here is an implementation strategy. Write

    parse_comments(String,Rep) :- string_codes(String,Codes), phrase(aScan(Rep),Codes).
    Here string_codes/2 and phrase/2 are standard predicates. You need to write a DCG clause for aScan.

Questions Due Thursday, 1 December

  1. Given the data type
    data LeafTree a = Leaf a | Branch (LeafTree a) (LeafTree a)
    write a function with signature
    removeIf :: (a -> Bool) -> LeafTree a -> Maybe (LeafTree a)
    that removes all of the elements from a given LeafTree that satisfy the given predicate. The result should be Nothing only when all of the elements have been removed.

    Hint: write a helper function

    branchMaybe ::  Maybe (LeafTree a) ->  Maybe (LeafTree a) ->  Maybe (LeafTree a)

    to join together two (Maybe) trees.

  2. Given the data type
    data Tree a = Empty  | Node a (Tree a) (Tree a)
    write a function with signature
    removeIf :: (a -> Bool) -> Tree a -> Tree a
    that removes all of the elements from a given Tree that satisfy the given predicate.

    Hint: write helper functions

    join ::  (Tree a) ->  (Tree a) ->  (Tree a)
    nodeMaybe :: (Maybe a) ->  (Tree a) ->  (Tree a) ->  (Tree a)

    to join together two trees or two trees and a value.

Questions Due Friday, 4 November

  1. A Collatz sequence starts with an arbitrary positive integer n. The next number in the sequence is
    • 3n+1 if n is odd, and
    • n/2 if n is even.
    A sequence ends when n reaches 1.
    1. Write a Racket program that repeatedly asks the user for a starting number and then displays the resulting Collatz sequence.
    2. Add a way for the user to terminate the program.
    3. Add test functions by using (require rackunit) .
    4. Write a similar program in Haskell.
  1. Write an uncurry function in Haskell so that if we have the definitions
       ff (a,b) = 2*a - 3 - b
       f  a  b  = 2*a - 3 - b
       g        = uncurry f
    then the functions ff and g work identically.
  2. (Reasoning as in the previous question) write a curry function in Racket.

Questions Due Tuesday, 4 October

  1. Read Chapter 2 of Learn You a Haskell for Great Good. Send me an e-mail message explaining what you understand to be the differences between lists and tuples.

    • Install Racket somewhere. Start up Racket.
    • Use the Help Centre to find the Racket Guide. Read Chapter 1 and Sections 2.1–2.
    • Send me an e-mail explaining how to write a function to compute <!-- a x^2 + b x + c --> from a, b, c, and x.
  2. Send me an e-mail explaining how to write a function to compute the function x a x 2 + b x + c from a, b, c, and x.
    • in Racket
    • in Haskell
    • in Java

  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?

Home page Semesters Site Map
go back Fall 2016 go forward
2017-09 other links

CPSC 320 [Other years]
CPSC 370 [Other years]
David’s Schedule

UNBC Undergraduate Calendar