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
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 from a, b, c, and x.
2. Send me an e-mail explaining how to write a function to compute the function from a, b, c, and x.
• in Racket
• 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?

 Fall 2016 2017-09

CPSC 320
CPSC 370
References
Homework
Dates
Policies
Resources
David’s Schedule