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

Assigned 2016-11-25

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

Assigned 2016-11-28

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

2016-10-31

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

from 2016-09-30

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.

from 2016-10-03

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

Questions Due Tuesday, 4 October

from 2016-09-14

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.
Send me an e-mail explaining how to write a function to compute the function $x \mapsto a x^{2} + b x + c$ from a, b, c, and x.
- in Racket
- in Haskell
- in Java

from 2016-09-19

How many partial functions are there from { Scissors, Paper, Rock, Spock, Lizard } ² to { Win, Lose } ?
How many of these are fair and interesting?

Questions Due Friday, 4 November

from 2016-09-30

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.

from 2016-10-03

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