COMP 3007 A/B (Winter 2024) “Programming Paradigms”
Specification for Assignment 06
Your submission for this assignment must be commented and must include both your name and your student number as a comment at the top of every source file you submit. Each of your submitted files must use a file name beginning:
comp3007_w24_#########_assignment_06_
…but with the ######### replaced with your official, nine-digit student number.
Officially, the due date for this assignment is: Friday, March 15th, 2023, at 11:59pm EST
Late submissions are accepted without penalty for up to 48-hours after that.
Any submissions that are not received until after that Sunday “cut-off” deadline will not be accepted under any circumstances and will always receive a mark of 0.
The objective of this assignment is allow you to practice with structural induction, for the purpose
of proving the correctness of a program. With the following collection of function definitions…
|
foo :: [Char] foo [] = 0 foo (h:t) = 1 |
-> Int + (foo t) |
qux :: Char -> qux x = ord x < |
Bool 80 |
ham :: Char -> Bool ham x = ord x > 81 |
|
|
bar :: [Char] |
-> [Char] |
xyz |
:: [Char] -> Int |
||
|
bar [] = [] |
xyz |
[] = 0 |
|||
|
bar (h:t) |
xyz |
(h:t) |
|||
|
| qux h = h : |
(bar t) |
| h |
== ‘P’ = 1 + (xyz t) |
||
|
| ham h = h : |
(bar t) |
| h |
== ‘Q’ = 1 + (xyz t) |
||
|
| otherwise = |
bar t |
| otherwise = xyz t |
|||
…prove, using structural induction, that, for any list of characters x… (foo x) – (foo (bar x)) = (xyz x)
For this assignment:
-
your submission must be a single pdf document that you created electronically (using a word processor like Microsoft Word or Google Docs), and please note that scans or digital photographs of handwritten submissions will not be accepted and will receive a mark of zero
-
you must include your full name and student number at the top of your submission, and you must copy the source code included above and provide an “identifier” for every line of source code (so that your proof can be “traced” by a teaching assistant)
-
you must show *all* your work (i.e., one “step” per line, the “name” of each step, and including *every* guard evaluation) in proving both the base case and the inductive case,
*separately* working the left-hand side and right-hand side of each expression, and you must
*explicitly* state your inductive assumption when proving the inductive case
-
you do not need to prove termination
Reviews
There are no reviews yet.