Midterm project
The goal of this midterm project is to give you a chance to reflect on
what you have been exposed to in this course since the beginning of the
semester, conceptually, practically, and methodologically.
Expectations
You are expected:
- to work in groups, as you did for the weekly handins, and
- to write an individual report, using your own words.
The individual report
Your report should include
- a front page with title, name, student number, and date,
- the names of the other members of your group,
- a second page with a table of contents, and
- from the third page and onward,
- an introduction,
- a series of sections and subsections reflecting the structure of the
project, and
- a conclusion where you assess what you did and reflect on how you did
it and the perspective your assessment and reflection provide.
Pages should be numbered, and the narrative should be spell checked.
An inspiring (and not necessarily humorous, just on topic) quote or three
would be welcome.
Throughout, remember to embrace the structure where the computation is
described informally (textually), where it is accounted for with a
unit-test function, where it is specified inductively, where this
inductive specification is mirrored into a structurally recursive
function, and where the implementation is verified to pass the unit
tests – unit tests whose limitations should be scrutinized.
About describing your programs: of course you should not paraphrase the
code, because what is the point of that.
A miscellany of recursive programs
- Exercise 3 in Week 06:
expressing the factorial function using fold_right_nat (optional, hard)
- Exercise 4 in Week 06:
the sumtorial function, revisited
- Exercise 5 in Week 06:
specifying and implementing the Sigma (a.k.a. sum) notation
- Exercise 6 in Week 06:
expressing fold_right_nat using parafold_right_nat (optional, not too hard) and
expressing parafold_right_nat using fold_right_nat (optional, very hard)
- Exercise 9 in Week 06:
implementing predicates for ternary, post-ternary, and pre-ternary non-negative integers
The underlying determinism of OCaml
- Question 2:
in which order are a function and an argument evaluated in an application?
- Question 3:
in which order are the definienses evaluated in a let expression?
- Question 4:
in which order are conjuncts evaluated in a Boolean conjunction?
- Question 5:
a warmup question
- Question 6:
implementing String.map with a simulated for-loop
- Question 7:
implementing String.mapi with a simulated for-loop
- Question 8:
determining the validity of a handful of simplifications
- Question 9:
determining the equivalence of let expressions involving impure expressions
- Question 10:
determining the equivalence of let expressions involving pure expressions
The case of the Fibonacci numbers
- Exercise 1:
expressing a Fibonacci function using fold_right_nat
- Exercise 2:
analyzing the traces of two Fibonacci functions
Palindromes, string concatenation, and string reversal
- Question 1:
implementing string concatenation using String.init
- Question 2:
implementing string reversal
- Question 3:
relating string concatenation and string reversal
- Question 4:
implementing palindrome generators
- Question 5:
implementing palindrome detectors
- Question 6:
implementing the reversal of a palindrome
- Question 7:
implementing a Fibonacci string (optional, not too hard)
More for the road
The two following exercises are optional.
- Exercise 7:
defining String.map using String.mapi (optional, easy)
- Exercise 8:
defining String.mapi using String.map and String.init
(optional, not very hard)
Exercise 7
Define String.map (a.k.a. Stringy.map) using String.mapi (a.k.a. Stringy.mapi).
Exercise 8
Define String.mapi (a.k.a. Stringy.mapi) using String.map
(a.k.a. Stringy.map) and String.init (a.k.a. Stringy.init).
Version
Added
Exercise 7
and
Exercise 8
on the ground that it is polite to prepare too much food when one has guests
[29 Feb 2020]
Completed
[22 Feb 2020]
Initialized (the actual content of the midterm project is forthcoming)
[22 Feb 2020]