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

CPSC 370: Functional and Logic Programming ( )

Pending homework questions

All questions are now due.

  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. <
    5. Write a similar program in Racket.
  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 ff
    then the functions f and g work identically.
  2. (Reasoning as in the previous question) write an curry function in Racket.
  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 (LeafTree a) (LeafTree 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.

  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.

Home page Semesters Site Map
go back Fall 2016 go forward
2022-12 other links

CPSC 320 [Other years]
CPSC 370 [Other years]
References
Homework
Dates
Policies
Resources
David’s Schedule

unbc Undergraduate Calendar