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

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

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`.    Fall 2016 2023-09 CPSC 320
CPSC 370
References
Homework
Dates
Policies
Resources
David’s Schedule