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?

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 ff```
then the functions `f` and `g` work identically.
2. (Reasoning as in the previous question) write an `curry` function in Racket.
 Fall 2016 2022-12

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