CPSC 370: Functional and Logic Programming ( Fall 2011 Fall 2012 Fall 2013 Fall 2015 Fall 2016 Fall 2017 Fall 2018 Fall 2019 Fall 2022 )

Pending homework questions

All questions are now due.

2016-09-30

5. 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 Racket.

2016-10-03

6. 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.
7. (Reasoning as in the previous question) write an curry function in Racket.

2016-10-31

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

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

2016-11-28

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