Some of you will find this assignment to be pretty easy but others may find it to be pretty hard. I recommend that you start on this assignment as soon as possible in case you find yourself in the latter group. Remember that as the syllabus states, late work is not accepted and there are no "late days", but I will consider extensions for circumstances beyond your control.
Haskell slides 1-228 show you all the elements of Haskell you need for this assignment, but the two sections that (will) follow in the slides, "Larger Examples" and "Errors", will broaden your understanding. My current thinking is to present the larger examples with recordings, so that you can fully control the pace of presentation for that relatively intricate material.
I often refer to assignments as "aN". This assignment is a3. This document is the "a3 write-up".
As you saw on a2 my assignment write-ups are a combination of education, specification, and guidance. My goal is for write-ups to need no further specification or clarification. That goal is rarely achieved. If you have questions you can either mail to 372f22 or post to Piazza using the appropriate aN folder.
This assignment has a long preamble that covers a variety of topics: the "Tester",
making an a3 symlink, some warnings about old solutions for recycled problems,
a very important section on assignment-wide restrictions, and more.
You might be inclined to skip all that stuff and get right to the problems, but I recommend you carefully read the preliminary material.
For programming problems great emphasis will be placed on the ability to deliver code whose output exactly matches the specification. Failing to achieve that will typically result in large point deductions, sometimes the full value of the problem.
I provide "the Tester", a testing script that you can use to confirm that the output of each of your solutions for the programming problems exactly matches the expected output for a number of test cases. Don't just "eyeball" your output—use the Tester! We won't have any sympathy for those who fail tests during grading simply because they didn't want to bother with the Tester! However, we'll be happy to help you with using the Tester and understanding its output.
The Tester is described in the document Using the Tester.
fall22/a3 directory
For each assignment there will be a subdirectory of /cs/www/classes/cs372/fall22 with assignment-specific files. Those directories will be named a2, a3, etc.
This write-up assumes your assignment 3 directory on lectura has an a3
symlink (symbolic link) that references the directory /cs/www/classes/cs372/fall22/a3, just like you made an a2
symlink that referenced .../fall22/a2 for assignment 2.
Let us know if you have trouble with this!
Just so there's no doubt about it, IT IS STRICTLY PROHIBITED TO POST PIECES OF SOLUTIONS on Piazza, whether they work or not.
If you can boil code down to a generic question, like "Why doesn't "f _ = _" compile?" or "Is there a function that produces the maximum value of a list of numbers?", that's ok.
If code has any trace of the problem or it conveys or implies anything about a solution, DON'T POST IT. A good rule of thumb is this: If it's apparent what problem some code is related to, that code should not be posted.
If you have even a minor concern that a Piazza post you're contemplating may reveal too much, mail to 372f22 instead.
When I started teaching here at The University of Arizona my aim, to combat cheating, was to come up with a great new set of problems for each assignment each time I taught a class. I eventually found I couldn't keep up with that standard. I noticed that sometimes an old problem was simply better than a new one. I began to reconsider my "all new problems every semester" goal and started thinking about questions like these:
I believe that students should be able to see the instructor's solutions, so I distribute solutions for almost all problems, although only in hardcopy form, to inhibit transmission to future students and/or the web at least a little bit.
If you should come into possession of one of my solutions from a past semester, whether it be from a "homework help" website, a friend who took the class, or some other source, let me encourage you to discard it! For one thing, I often put dunsels in my solutions.
Here's some Haskell code with a dunsel:
add x y = x + y + 0That "
+ 0" is a dunsel—it serves no purpose. That dunsel is easy to spot but I try to have
better dunsels in my solutions.
I'd like to distribute solutions with perfectly clean and idiomatic code but I've found that a few dunsels—extra parts that stick out like a sore thumb—and that the lazy don't tend to notice, help me eliminate students who find and reuse my solutions. If you notice a silly extra in my code, try removing it and see if things still work. If so, you've perhaps found a dunsel!
Here's how dunsel entered my vocabulary.
A further disincentive for cheating is that I've kept copies of all former students' submissions for a given problem. We use publicly available tools like MOSS and a suite of software I've developed to look for suspicious similarities both in the set of this semester's submissions and in that set combined with submissions from all previous semesters when the problem was used.
The very first cheating case I ever prosecuted involved an "atoi" (ASCII-to-integer)
function in Standard ML.
Back then (1996) we'd run the students' solutions for a given problem, print the results on
a stack of fanfold paper, and then my TA and I would grab our red pens and grade our way
through each problem's stack of paper in turn.
My TA and I were grading atoi solutions and I said something like, "Ouch! This guy got
-23497893 for atoi "1234" (instead of 1234). My TA looked at
what he was grading and said, "Uh-oh—so did this one!"
It so happened, in a stroke of bad luck for a couple of cheaters, that their UNIX logins were consecutive in lexicographic order, and that's the order in which we tested solutions, printed listings, and graded solutions. Their identical solutions were back-to-back in the fanfold stack!
A practice I learned from that early episode is to test all submissions, both new and archived, with some invalid inputs when practical. If two solutions produce interestingly identical garbage out for some particular garbage in, those solutions are perhaps worth a closer look. (See also GIGO.)
Remember my cheating policy: one strike and you're out! For a first offense, on just a single problem, no matter how few points the problem is worth, expect these penalties:
The syllabus section, Code of Academic Integrity goes into more detail. Of all the things I say in the syllabus about cheating, nothing is more true than this:
I am happy to spend hours helping a student who is earnestly trying to learn the material, but I truly loathe every minute spent on academic integrity cases.
Cheating is a choice, and a bad one, sometimes made when students think they have no alternatives. If you find yourself about to cheat because you think you're sunk, talk to me instead!
head, tail, and !!
Once you "get it" with Haskell patterns you'll find that you rarely want to use
the head or tail functions. Having said that, however, one example of
a reasonable place to use tail is
for a tweak of a near-final result, like a list whose first element needs to be discarded.
Similarly, if you're processing lists with patterns, you should have little need for the indexing operation, !!. (I don't use it in any of my solutions.) If you find yourself making much, if any, use of !!, you're probably recursing on integer values rather than on tails of lists—a recursive Java solution written in Haskell!
Code that makes significant unnecessary use of head, tail, and/or !! is subject to minor deductions.
A key to success in this class is not forgetting everything you've learned about programming just because you're working in a new language.
The skills you've learned in other classes for breaking problems down into smaller problems will serve you well in
Haskell, too.
On the larger problems, particularly a4's squares and editstr, look for small functions to write first that you can then build into larger functions. Test those functions one at a time, as they're written.
If you don't see the cause of a syntax or type error in an expression, whittle down the code until you do. Or, start with something simple and build towards the desired expression until it breaks.
You'll probably have some number of errors due to surprises with precedence. Adding parentheses to match the precedence you're assuming may reveal a problem.
I think of a bug as a divergence between expectation and reality. A key skill for programmers is being able to work backwards to find where that divergence starts. Here's an example of working backwards from an observed divergence to its source:
Once upon a time, I was stumped by a type error in this Haskell expression:
"#" ++ show lecNum ++ " " ++ [dayOfWeek] ++ " "
: classdays' (lecNum+1) (first+daysToNext) last pairs
I first wondered if the error would persist if the list being produced by
classdays' was replaced by an empty list:
"#" ++ show lecNum ++ " " ++ [dayOfWeek] ++ " "
: []
The error remained. I then produced a trivial case that worked by simply adding "--" (Haskell's comment-to end-of-line) after the "#", hiding the rest of the expression on the first line:
"#" -- ++ show lecNum ++ " " ++ [dayOfWeek] ++ " "
: []
That worked. I then tried advancing "--" past the show lecNum call:
"#" ++ show lecNum -- ++ " " ++ [dayOfWeek] ++ " "
: []
The error returned! I then tried a very simple equivalent expression:
"a" ++ "b" : []It produced the original type error! I checked the precedence chart. (Slide 111.) I also used
:info to look at the ++ and "cons" operators:
> :info (++) (++) :: [a] -> [a] -> [a] infixr 5 ++ > :info (:) data [] a = ... | a : [a] infixr 5 :Since both
++ and : are right-associative operators (infixr) with equal precedence (5), the operator on the right, the :, is done first.
Effectively,
"a" ++ "b" : []means
"a" ++ ("b" : [])
and that was the divergence between expectation and reality: I expected
"a" ++ "b" : []to group as
("a" ++ "b") : []
but the reality was the opposite!
If you're puzzled by a syntax or type error, make an effort to whittle down the code a little before you send it to us.
If you get it down as far as I did with "a" ++ "b" : [], then you've got a GREAT question!
And, something as simple as "a" ++ "b" : [] can clearly be posted on Piazza for all to see,
without any worry about giving away part of a solution (which would cause me to give you a lot of grief!)
Quite often the first thing we'll want to do when you tell us about a problem you're having is to reproduce that problem ourselves. That means we need to know (1) what you typed, (2) what you saw, and (3) what your source code is.
Copy/pasted text of interaction with a REPL or Bash is usually the best way to cover (1) and (2). For example, here's an error:
% ghci warmup.hs GHCi, version 8.10.7: ... [1 of 1] Compiling Main ( warmup.hs, interpreted ) warmup.hs:10:5: error: parse error on input ‘|’ | 10 | | n == 0 = [] | ^ Failed, no modules loaded. >When I see the above interaction the next thing I want to do is to look at
warmup.hs.
The best way for you to get your code to us is to use a3/turnin.
Do that and BE SURE to mention in your message that you've run a3/turnin.
a3/turnin will turn in all existing deliverables and you might think that's a waste
or creates a lot of clutter, etc., but it's simply the expedient thing to do!
Along with doing a3/turnin, you might include an excerpt with where you think
the problem lies and share your thoughts on it. Novices tend to look in the wrong places for an error
but sometimes that process of talking about a problem will help you find it yourself.
For the problems you'll be doing this semester, which will likely be 100% text-based, I can't think of a case where a screenshot will be useful to us. A particularly worthless thing is a screenshot with side-by-side windows, with one showing interaction with an error and the other showing source code. We'd have to type in your code to try running it ourselves! If you don't know how to get text from a window onto the clipboard, let us know.
There are three assignment-wide restrictions on this assignment:
Data.Char.
You can use Prelude functions as long as they are not higher-order functions (see third restriction).
Exception: imports you used to aid development, such as Text.Show.Functions and Debug.Trace, need not be removed.
[ expression | qualifier1, ..., qualifierN ]. That vertical bar after the initial expression is the most obvious characteristic of a list comprehension.
I believe that map is the only higher-order function I've shown you thus far. Here it is again:
> words "a few words here" ["a","few","words","here"] > map length it [1,3,5,4] > :t map map :: (a -> b) -> [a] -> [b]
Note the type of map's first argument: (a -> b). The -> in that type tells us
that it's a function. The surrounding parentheses are needed because without them it would mean that map takes three arguments: an a, a b, a list of as, and returns a list of bs.
We'll be learning about higher-order functions soon, and you'll see that we can use them instead of writing recursive functions in many cases, but for now I want you writing only recursive functions—think of it as getting good at walking before trying to run.
Here is, I believe, a full list of all higher-order functions in the Prelude:
all any break concatMap curry dropWhile either filter flip foldl foldl1 foldr foldr1 interact iterate map mapM mapM_ maybe scanl scanl1 scanr scanr1 span takeWhile uncurry until zipWith zipWith3
:type on some of them and look for argument types with (... -> ...),
(... -> ... ->), etc.
Whenever an assignment has restrictions or other potential losses of points unrelated to correct behavior,
we're always willing to take a look at your code before it's due to see if there are any violations. Just mail it to 372f22. Such inspections are done as time permits.
Slides 120+ talk about specifying types for functions but here's a little more about that.
The following function has an error.
f ((x,y,z):t) index len
| (index `mod` length) == 0 = ""
Here's the type that Haskell infers for that erroneous function:
f :: Integral ([a] -> Int) =>
[(t1, t2, t3)] -> ([a] -> Int) -> t -> [Char]
Whoa! Where'd that ([a] -> Int) for the second argument, index, come from?
If you look closely, you'll see that instead of using the parameter len, the guard inadvertently uses length, a Prelude function.
Since the type of mod is Integral a => a -> a -> a, Haskell proceeds to infer that this function needs a second argument that's an [a] -> Int function which is an instance of the
Integral type class.
I can't think of any use for such a thing, but Haskell proceeds with that inferred type and bases subsequent type inferences on the assumption that the inferred type of f is correct. That can produce far-flung false positives for errors in other functions.
Preceding the clause for f with a specification for the intended type of f leads to a good error message:
% cat extype.hs
f::[(Int,Int,Char)] -> Int -> Int -> String -- The intended type
f ((x,y,z):t) index len
| (index `mod` length) == 0 = ""
% ghci extype.hs
...
extype.hs:3:20: error:
• Couldn't match expected type 'Int'
with actual type 't0 a0 -> Int'
• In the second argument of 'mod', namely 'length'
In the first argument of '(==)', namely '(index `mod` length)'
In the expression: (index `mod` length) == 0
|
3 | | (index `mod` length) == 0 = ""
| ^^^^^^
Failed, 0 modules loaded.
The downside of specifying a type for a function is that we might inadvertently make a function's type needlessly specific, perhaps by using an Int or Double when an instance of the Num type class would be better.
My usual practice is to see what type Haskell infers for a newly written function. If it looks reasonable, I then "set it in stone" by adding a specification for that type. If an apparent type problem arises later, I might try temporarily commenting out that type specification to help get a handle on the problem.
warmup.hs and ftypes.hs
In general, writing helper functions to break a computation into smaller, simpler pieces is a great practice. However, the functions in warmup.hs, the first problem, are simple enough that you shouldn't need a helper to write any of them. The last problem on the assignment, ftypes.hs, has a number of problem-specific restrictions, including no helper functions.
Aside from warmup.hs and ftypes.hs, it's fine to use helper functions throughout this assignment.
Prelude documentation for version 8.6.5, the version of GHC on lectura, is here: hackage.haskell.org/package/base-4.12.0.0/docs/Prelude.html.
Prelude documentation for version 8.10.7, the version of GHC you most likely got if you installed it on your machine, is here: hackage.haskell.org/package/base-4.14.3.0/docs/Prelude.html.
Documentation entries typically have "Source" links, but you'll find that many functions are written using elements of Haskell we haven't seen.
You can see a list of all Prelude functions by using :browse Prelude at the ghci prompt.
warmup.hs
The purpose of this problem is to get you warmed up by writing your own version of several simple functions from the Prelude: last, init, replicate, drop, take, elem and ++.
The code for these functions is easy to find on the web and in books—a couple are shown as examples of recursion in LYAH. Whether or not you've seen the code I'd like you first to try writing them from scratch. If you have trouble, go ahead and look for the code. Study it, but then put it away and try again to write the function from scratch. Repeat as needed. Think of writing these functions as being like practicing scales on a musical instrument.
To avoid conflicts with the Prelude functions of the same name, use these names for your versions:
| Prelude function | You call it |
| last | lst |
| init | initial |
| replicate | repl |
| drop | drp |
| take | tk |
| elem | has |
| (++) | concat2 |
You should be able to write these functions using only pattern matching, comparisons in guards, list literals, cons (:), simple arithmetic, and recursive calls to the function itself. If you find yourself about to use if-else, see if
you can use a guard instead.
concat2 is a function that's used exactly like you'd use the ++ operator as a function:
> concat2 "abc" "xyz" "abcxyz" > (++) "abc" "xyz" -- see slide 94 "abcxyz"You may find that
concat2 is the most difficult of the bunch—it's simple but subtle.
Experiment with the Prelude functions to see how they work. Note that replicate, drop, and take use a numeric count. Experiment with the Prelude versions to see how they behave with zero and negative values for their count. Remember that unary negation typically needs to be enclosed in parentheses:
take (-3) "testing"
You'll find that last and init throw an exception if called with an empty list. You can handle that with a clause like this one for lst:
lst [] = error "emptyList"
As I hope you'd assume, you can't use the Prelude function that you are recreating. Beware that when writing these reproductions it's easy to forget and use the Prelude function by mistake, like this:
drp ... = ... drop ...Here's an
egrep command you can use to quickly check for accidental use of the Prelude functions in your solution: (in a3/check-warmup)
egrep -w "last|init|replicate|drop|take|elem|\+\+" warmup.hs
Testing note: If you run the Tester with a3/tester warmup, you'll see that it runs tests for all of the expected functions, producing a long stream of failures for any functions you haven't completed. You can test functions one at a time by using a -t option following warmup:
% a3/tester warmup -t lst ... % a3/tester warmup -t drp ...
join.hs
Write a function join separator strings of type [Char] -> [[Char]] -> [Char] that concatenates the strings in strings into a single string with separator between each. Examples:
> join "." ["a","bc","def"] "a.bc.def" > join ", " ["a", "bc"] "a, bc" > join "" ["a","bc","def", "g", "h"] "abcdefgh" > join "..." ["test"] "test" > join "..." [] "" > join ".." ["","","x","",""] "....x...." > join "-" (words "just testing this") "just-testing-this"
In Java you might use a counter of some sort to know when to insert the separators but that's not the right approach in Haskell.
rme.hs
Write a function rme n of type Integral a => a -> a that, using an arithmetic approach, removes the even digits from n, which is assumed to be greater than zero.
Examples:
> rme 3478 37 > rme 100100010010 1111 > rme (17^19) 39735515137153
Important: Your solution must be based on arithmetic operations like *, -, and div rather than doing something like using show to turn n into a string, and then processing that string with list operations.
An obvious difficulty is posed by numbers consisting solely of even digits, like 2468. For such numbers, rme produces zero:
> rme 2468 0
splits.hsConsider splitting a list into two non-empty lists and creating a 2-tuple from those lists.
For example, the list [1,2,3,4] could be split after the first element to produce the tuple ([1],[2,3,4]). In this problem you are to write a function splits of type [a] -> [([a], [a])] that produces a list of tuples representing all the possible splits of the given list.
Examples:
> :type splits
splits :: [a] -> [([a], [a])]
> splits [1..4]
[([1],[2,3,4]),([1,2],[3,4]),([1,2,3],[4])]
> splits "xyz"
[("x","yz"),("xy","z")]
> splits [True,False]
[([True],[False])]
> length (splits [1..50])
49
A list must contain at least two elements to be splittable. If splits is called with a list that has fewer than two elements, raise the exception shortList. Example:
> splits [1] *** Exception: shortList
In case you missed it, there's an example of raising an exception in the write-up for Problem 1, regarding
lst.
cpfx.hs
Write a function cpfx, of type [[Char]] -> [Char] that produces the common prefix, if any, among a list of strings.
If there is no common prefix or the list is empty, return an empty string. If the list has only one string, then that string is the result.
Examples:
> cpfx ["abc", "ab", "abcd"] "ab" > cpfx ["abc", "abcef", "a123"] "a" > cpfx ["xabc", "xabcef", "axbc"] "" > cpfx ["obscure","obscures","obscured","obscuring"] "obscur" > cpfx ["xabc"] "xabc" > cpfx [] ""
paired.hs
Write a function paired s of type [Char] -> Bool that returns True iff (if and only if) the parentheses in the string s are properly paired, like they would be in an algebraic expression.
Examples with properly paired parentheses:
> paired "()" True > paired "(a+b)*(c-d)" True > paired "(()()(()))" True > paired "((1)(2)((3)))" True > paired "((()(()()((((()))))((())))))" True > paired "" True
Examples with improper pairing:
> paired ")"
False
> paired "("
False
> paired "())"
False
> paired "(a+b)*((c-d)"
False
> paired ")("
False
Note that you need only pay attention to parentheses:
> paired "a+}(/.$#${)[[["
True
> paired"a+}(/.$#$([[)["
False
ftypes.hs
Slides 112+ demonstrate that Haskell infers types based on how values are used.
Your task in this problem is to create a sequence of operations on function arguments that cause each of five functions, fa, fb, fc, fd, and fe to have a specific inferred type.
The functions will not be run, only loaded, and need not perform any meaningful computation or even terminate.
Here are the types, shown via interaction with ghci:
% ghci ftypes.hs ... [1 of 1] Compiling Main ( ftypes.hs, interpreted ) Ok, modules loaded: Main. > :browse fa :: Int -> Bool -> Char -> (Char, Int, Bool) fb :: [Bool] -> [Int] -> Char -> String fc :: (Num t1, Num t) => [(t1, t)] -> (t, t1) fd :: (Integer, [a]) -> Int -> Bool fe :: [[Char]] -> [[a]]To make this problem challenging we need to have some restrictions:
No apostrophes ('), double-quotes (") or decimal digits may appear in ftypes.hs, not even in comments. (Yes, this makes character, string, and numeric literals off-limits!)
True or False.
::Int (introduced on slide 67).
fst or snd functions from the Prelude.
where clause, or let, do,
or case expressions.
if-else.
Violation of a restriction will result in a score of zero for that function.
Depending on your code you might end up with a type that's equivalent to a desired type but
that has type variables with names that differ from those shown above. For example, fc is shown above as this,
fc :: (Num t1, Num t) => [(t1, t)] -> (t, t1)but the Tester will consider the following to be correct, too:
fc :: (Num a, Num b) => [(a, b)] -> (b, a)If you look close, you'll see that the only difference is that the former uses the type variables
t1 and t
instead of a and b, respectively.
Similarly, the following type would also be considered correct:
fc :: (Num t, Num a) => [(t, a)] -> (a, t)
observations.txt
Submit a plain text file named observations.txt with...
(a) (1 point extra credit) An estimate of how many hours it took you to complete this assignment. Put that estimate on a line by itself, like this:
Hours: 3.5There should be only one
"Hours:" line in observations.txt. (It's fine if you care to provide per-problem times, and that data is useful to us, but report it in some form of your own invention that doesn't contain the string "Hours:". Thanks!)
Feedback and comments about the assignment are welcome, too. Was it too long, too hard, too detailed? Speak up! I appreciate all feedback, favorable or not.
(b) (1-3 points extra credit) Cite an interesting course-related observation (or observations) that you made while working on the assignment. The observation should have at least a little bit of depth. Think of me thinking "Good!" as one point, "Excellent!" as two points, and "Wow!" as three points.
Note: I'm looking for quality, not quantity—over the years I've given three points to some one-liners, and single points to lots of long essays in observations.txt.
Use a3/turnin to submit your work, just like you used a2/turnin on assignment 2. Example:
% pwd /home/whm/hbcurry/CSC372/asn2 % a3/turnin ======== contents of a3.20220911.175357.tz ======== -rw------- hbcurry/root 1759 2018-01-28 01:51 warmup.hs -rw-r--r-- hbcurry/root 183 2018-01-28 01:51 join.hs -rw-r--r-- hbcurry/root 179 2018-01-28 01:51 rme.hs -rw-r--r-- hbcurry/root 238 2018-01-28 01:51 splits.hs -rw-r--r-- hbcurry/root 144 2018-01-28 01:51 cpfx.hs -rw-r--r-- hbcurry/root 228 2018-01-28 01:51 paired.hs -rw-r--r-- hbcurry/root 386 2018-02-08 14:44 ftypes.hs -rw------- hbcurry/root 2184 2022-09-11 17:53 observations.txt ======== running turnin ======== Turning in: a3.20220911.175357.tz -- ok All done. %
Each run of a3/turnin creates a time-stamped "tar file" in your current directory with a name like
a3.YYYYMMDD.HHMMSS.tz that contains a copy of each of the deliverables
specified in a3/delivs. You can run a3/turnin as often as you want.
We'll grade your final pre-deadline submission.
a3/turnin -l shows your submissions.
To give you an idea about the sizes of my solutions, here's what I see as of press time:
% wc $(grep -v txt < a3/delivs) 29 115 491 warmup.hs 3 21 81 join.hs 8 42 215 rme.hs 6 34 202 splits.hs 8 38 171 cpfx.hs 8 51 278 paired.hs 12 60 278 ftypes.hs 74 361 1716 totalMy code has few comments.
Note that each of the a3.*.tz files created in your directory by a3/turnin is essentially a
time-stamped backup of your code. Feel free to use a3/turnin whenever you've reached a milestone and
want to save a copy of it.
If you should ever want to retrieve an old version of a file from an aN.*.tz file but you aren't familiar with tar, perhaps mail to 372f22 for assistance—it's easy to accidentally clobber a current version.
If like me you've experienced the power of Murphy's Law in your life, you might periodically copy a just-made aN.*.tz file from lectura to your own machine using scp, WinSCP, or something similar.
Also, you can email yourself a copy of whatever deliverables you've created like this:
% pr $(cat a3/delivs) | mail -s 'a3 latest' your-NETID
The message will go to your-NETID@cs.arizona.edu and should appear in your CatMail within seconds.
The -s option specifies the Subject of the email message. Surround it with apostrophes if it contains
any whitespace or shell metacharacters.
You might celebrate with a milestone in the subject:
% pr $(cat a3/delivs) | mail -s '372 cpfx works!' whm pr: splits.hs: No such file or directory pr: ftypes.hs: No such file or directory pr: observations.txt: No such file or directoryIf you haven't created some of the deliverables yet, you'll see errors like above, but all existing deliverables will be included.
The above, with -s "372 cpfx works!" works, but—long story involving Bash's history
mechanism—including exclamation marks in the subject can be problematic. You might get an error with "event not found", and no message will be sent.
Finally, Rule Number One with backups is, Check your backups before you need to use one of them! As soon as you've got some code saved in one of the deliverables, try mailing yourself a backup. Be sure the message has the code you expected. Repeat the process when you've made a second deliverable. Lather, rinse, repeat until fear turns into boredom.
Point values of problems correspond closely to the "assignment points" mentioned in the syllabus. For example, a 10-point problem would correspond to about 1% of your final grade in the course.
Feel free to use comments to document your code as you see fit, no comments are required in your code.
In Haskell, two minus signs (--) is comment to end of line, like // in Java; {- and -} are used to enclose block comments,
like /* and */ in Java.
Remember that late assignments are not accepted and that there are no late days; but if circumstances beyond your control interfere with your work on this assignment, there may be grounds for an extension. See the syllabus for details.
My estimate is that it will take a typical CS junior from 5 to 10 hours to complete this assignment.
Our goal is that everybody gets 100% on this assignment AND gets it done in an amount of time that is reasonable for them.
We hope you'll make use of Piazza, email and office hours if problems arise. If you're getting toward eight hours into this assignment and don't seem to be close to completing it, or you're simply worried about your "slope", email us! Give us a chance to speed you up!
Historically speaking, I've seen a lot of students really struggle with the simple.hs functions
but then find themselves able to make steady progress thereafter.
I'm sorry to say, and I apologize for it, that some bad planning early on, and my poor pace on some slides led to a quandary when trying to set a deadline for assignment 3. I wanted to have a Friday night deadline but September 23 seemed pretty aggressive, and September 30 seemed pretty slack.
My "solution", and we'll see how well it works, is to have assignment 3 comprise the problems above and move two large problems I'd pictured for assignment 3 to assignment 4 instead.
The write-ups for the two problems I'm shifting out of assignment 3, squares and editstr,
follow below so that you can get an early start on them if you wish. I consider their
write-ups to be final aside from being subject to correction or clarification if needed.
Ideally, I'd like to see you finish the assignment 3 problems (above) and have made some good progress on
squares and editstr (below) by the assignment 3 deadline. I know that
"some good progress" is pretty nebulous. One example of some good progress would be to mostly understand
the computations being done by both squares and editstr.
Another example would be to have either
squares or editstr working for some simple cases.
I currently picture Assignment 4 being due on September 30. Along with squares and editstr,
it may have a few small problems, too.
squares.hs
Write a function drawSquares squares, of type [Square] -> IO () that renders an
ASCII "image" of the squares.
A square is represented with a four-tuple that specifies the square's upper-left corner (x and y coordinates),
its size (i.e., width and height),
and a two-character string that specifies the square's border and fill characters.
For example, (8,4,5,"*+") specifies a square with its upper-left corner at (8,4);
a width and height of 5;
and '*' and '+' for its border and fill characters, respectively.
Like String on slide 156, Square is a type synonym:
type Square = (Int,Int,Int,[Char])
The upper-left corner of the ASCII "image" is (0,0). The bounds of the image are calculated
such that it fully contains all the squares, and have an empty row/column on the bottom/right. Coordinates and sizes are assumed to be non-negative. The border and fill string is assumed to be exactly two
characters.
Here's an example with one square:
> drawSquares [(2,2,5,"+-")] ........ ........ ..+++++. ..+---+. ..+---+. ..+---+. ..+++++. ........
Note that drawSquares, like printN and charbox in the section
A little output (slide 168+), produces output.
To avoid tangling with the details of I/O in Haskell on this assignment, make your drawSquares function
look like this:
drawSquares :: [Square] -> IO ()
drawSquares squares = putStr result
where
...some number of expressions and helper functions that
build up `result`, a string...
The string result will need to have whatever characters and newlines are required, and that's the challenge of this
problem—figuring out how to build up that multiline string!
To help, and hopefully not confuse, here's a trivial version of drawSquares that's "hardwired" for
this one-Square list: [(1,1,3,"+-")]
drawSquaresHW _ = putStr output
where
output = ".....\n.+++.\n.+-+.\n.+++.\n.....\n"
Execution:
> drawSquaresHW [(1,1,3,"+-")] ..... .+++. .+-+. .+++. .....As I said, I hope that
drawSquaresHW example doesn't confuse! It's intended to show the connection between
result to a string that represents the image
putStr with result
Here's a drawing with four squares:
> drawSquares [(2,2,5,"Aa"), (12, 0, 4, "Bb"), (9,5,3,"C "),
(17,8,1, "Dd")]
............BBBB...
............BbbB...
..AAAAA.....BbbB...
..AaaaA.....BBBB...
..AaaaA............
..AaaaA..CCC.......
..AAAAA..C C.......
.........CCC.......
.................D.
...................
Due to character cells themselves not being square, the "squares" aren't square either. We'll ignore this.
If squares overlap, squares appearing later in the list are drawn on top of earlier squares. Examples:
> drawSquares [(8,4,5,"**"), (1,1,10,"@@"), (3,5,3,"+ ")]
..............
.@@@@@@@@@@...
.@@@@@@@@@@...
.@@@@@@@@@@...
.@@@@@@@@@@**.
.@@+++@@@@@**.
.@@+ +@@@@@**.
.@@+++@@@@@**.
.@@@@@@@@@@**.
.@@@@@@@@@@...
.@@@@@@@@@@...
..............
> drawSquares (reverse [(8,4,5,"**"), (1,1,10,"@@"),
(3,5,3,"+ ")])
..............
.@@@@@@@@@@...
.@@@@@@@@@@...
.@@@@@@@@@@...
.@@@@@@@*****.
.@@@@@@@*****.
.@@@@@@@*****.
.@@@@@@@*****.
.@@@@@@@*****.
.@@@@@@@@@@...
.@@@@@@@@@@...
..............
The character '#' has special meaning when used as a fill character: it specifies a transparent fill.
Here's the previous example, but with a transparent fill for the square. We can see through the @ square
to the squares underneath it.
> drawSquares [(8,4,5,"**"), (1,1,10,"@#"), (3,5,3,"+ ")] .............. .@@@@@@@@@@... .@........@... .@........@... .@......**@**. .@.+++..**@**. .@.+ +..**@**. .@.+++..**@**. .@......**@**. .@........@... .@@@@@@@@@@... ..............
Assume that drawSquares is never called with an empty list.
editstr.hs
For this problem you are to write a function editstr ops s that applies a sequence of operations (ops) to a string s and returns the resulting string. Here is the type of editstr:
> :type editstr editstr :: [([Char], [Char], [Char])] -> [Char] -> [Char]Note that
ops is a list of tuples. One of the available operations is replacement. Here's a tuple that specifies that every blank is to be replaced with an underscore:
("rep", " ", "_")
Another operation is translation, specified with "xlt".
("xlt", "aeiou", "AEIOU")
The above tuple specifies that every occurrence of "a" should be translated to "A", every "e" to "E", etc. A tuple such as ("xlt", "aeiouAEIOU", "**********") specifies that all vowels should be translated to asterisks.
Here are two cases we won't test with xlt:
("xlt", "aa", "12")
("xlt", "tab", "bat")
Here is an example of a call that specifies a sequence of two operations, first a replacement and then a translation:
> editstr [("rep", " ", "_"), ("xlt", "aeiou", "AEIOU")]
"just a test"
"jUst_A_tEst"
Note that for formatting purposes the example above and some below are broken across lines.
For "rep" (replace), the second element of the tuple is assumed to be a one-character string. The third element, the replacement, is a string of any length. For example, we can remove "o"s and triple "e"s like this:
> editstr [("rep", "o", ""), ("rep", "e", "eee")] "toothsomeness"
"tthsmeeeneeess"
Another example:
> editstr [("xlt", "123456789", "xxxxxxxxx"), ("rep", "x", "")]
"5203-3100-1230"
"0-00-0"
There are three simpler operations, too: length (len), reverse (rev), and replication (x):
> editstr [("len", "", "")] "testing"
"7"
> editstr [("rev", "", "")] "testing"
"gnitset"
> editstr [("x", "3", "")] "xy"
"xyxyxy"
> editstr [("x", "0", "")] "the"
""
Implementation note: The replication operation ("x") requires conversion of a string to an Int. That can be done with the Prelude's read function. Here's an example:
> stringToInt s = read s::Int > stringToInt "327" 327Note that
read does not do input! What it is "reading" from is its string argument, like
Integer.parseInt() in Java. Because read is polymorphic,
we use ::Int to specifically request an Int.
Assume the replication count for "x" represents a non-negative integer. We simply
won't test with something like ("x", "-3", ""), or ("x", "oops", ""),
or ("x", "", ""), etc.
Toward the end of our Haskell material we'll see that we can create new types using a data declaration,
and that something like data StrOp would be perfect for this problem. For the time being, however,
we're limiting ourselves to a low-tech approach based on a list of three-tuples for operations.
And, for "len", "rev", and "repl", not all three values in the
tuples are used. The upshot is that we've got a lot of "punctuation noise"!
Let's define some tuple-creating functions and simple value bindings so that we can specify operations with much
less noise. Put the following lines in your editstr.hs.
rep from to = ("rep", from, to)
xlt from to = ("xlt", from, to)
len = ("len", "", "")
rev = ("rev", "", "")
x n = ("x", show n, "") -- Note: show converts a value to a string
Recall this example above:
editstr [("xlt", "123456789", "xxxxxxxxx"), ("rep", "x", "")]
"5203-3100-1230"
Let's redo it using the rep and xlt bindings from above.
>editstr [xlt "123456789" "xxxxxxxxx", rep "x" ""] "5203-3100-1230" "0-00-0"Note that instead of specifying two literal tuples as operations, we're specifying two function calls that create tuples instead. Notice that
editstr's first argument, a list with two expressions, turns into a list with two operation tuples:
> [xlt "123456789" "xxxxxxxxx", rep "x" ""]
[("xlt","123456789","xxxxxxxxx"),("rep","x","")]
Here's a more complex sequence of operations:
> editstr [x 2, len, x 3, rev, xlt "1" "x"] "testing" "4x4x4x"Operations are done from left to right. The above specifies the following steps:
"testingtesting".
"14".
"141414".
"414141".
"1"s into "x"s, producing "4x4x4x"
Again, in case it helps you understand what the x, len, rev, etc. bindings are all about, let's see what that first argument to editstr turns into:
> [x 2, len, x 3, rev, xlt "1" "x"]
[("x","2",""),("len","",""),("x","3",""),("rev","",""),
("xlt","1","x")]
Incidentally, this is a simple example of an internal DSL (Domain Specific Language) in Haskell.
An expression like [x 2, len, x 3, rev, xlt "1" "x"] is using the facilities of Haskell to specify computation
in a new language that's specialized for string manipulation.
This write-up is already long enough so I won't say anything about DSLs here but you can Google and learn!
What we now call Domain Specific Languages were often called "little languages" years ago.
The list of operations can be arbitrarily long. If the list of operations is empty, the original string is returned.
> editstr [] "test" "test"The exception
badSpec is raised to indicate any of three error conditions:
"rep", "xlt", "rev", "len", or "x".
"rep", the length of the string being replaced is not one.
"xlt", the two strings are not the same length.
Here are examples of each, in turn:
> editstr [("foo", "the", "bar")] "test"
"*** Exception: badSpec
> editstr [("rep", "xx", "yy")] "test"
"*** Exception: badSpec
> editstr [("xlt", "abc", "1")] "test"
"*** Exception: badSpec
Here's what I see at the moment for my versions of squares.hs and editstr.hs,
which have few comments:
% wc squares.hs editstr.hs 78 492 2774 squares.hs 49 270 1483 editstr.hs 127 762 4257 total