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 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.
Write a Racket program that
repeatedly asks the user for a starting number and then
displays the resulting Collatz sequence.
Add a way for the user to terminate the program.
Add test functions by using
(require rackunit)
.
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
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 } ^{2}
to { Win, Lose } ?