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-226 show you all the elements of Haskell you need for this assignment. The next two sections in the slides, "Errors", and "Debugging", will help you deal with problems. Following those, the section "Larger Examples" will broaden your understanding.
I often refer to assignments as "aN
". This assignment is a3
. This document is the "a3
write-up".
On a2
you saw that 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 372s23
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.
spring23/a3
directory
For each assignment there will be a subdirectory of /cs/www/classes/cs372/spring23
with assignment-specific files. Those directories will be named a2
, a3
, etc.
This write-up assumes your assignment 3 directory on lectura—where your solutions will be—has an a3
symlink (symbolic link) that references the directory /cs/www/classes/cs372/spring23/a3
, just like you made an a2
symlink that referenced .../spring23/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 372s23
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 have no alternative, 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 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 pairsI 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 110. 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.
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.6.5: ... [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'll 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
, Text.Show.Functions
and Debug.Trace
.
You can use Prelude functions as long as they are not higher-order functions (see third restriction).
[ 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 a
s, and returns a list of b
s.
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
Try :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 372s23
. Such inspections are done as time permits.
Slides 119+ 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" "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.hs
Consider 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]) 49A 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 ")(" FalseNote that you need only pay attention to parentheses:
> paired "a+}(/.$#${)[[[" True > paired"a+}(/.$#$([[)[" False
squares.hs
Write a function drawSquares squares
, of type [Square] -> IO ()
that prints an
ASCII "image" of the Square
s in the list 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—it's a square),
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 155, 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 has an empty row/column on the bottom/right.
Make these assumptions:
drawSquares
is never called with an empty list.
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 167+), produces output.
To avoid tangling with the details of I/O in Haskell for this problem, start your drawSquares
function
with the following three lines of code:
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 result where result = ".....\n.+++.\n.+-+.\n.+++.\n.....\n"Execution:
> drawSquaresHW () -- "unit" (slide 169) for its unused parameter ..... .+++. .+-+. .+++. .....Again, I hope that
drawSquaresHW
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,2,"Dd")] ............BBBB.... ............BbbB.... ..AAAAA.....BbbB.... ..AaaaA.....BBBB.... ..AaaaA............. ..AaaaA..CCC........ ..AAAAA..C C........ .........CCC........ .................DD. .................DD. ....................Due to character cells themselves not being square, the "squares" aren't square either. Their aspect ratio is actually close to 1:2 but we'll ignore that!
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,"+ ")]) .............. .@@@@@@@@@@... .@@@@@@@@@@... .@@@@@@@@@@... .@@@@@@@*****. .@@@@@@@*****. .@@@@@@@*****. .@@@@@@@*****. .@@@@@@@*****. .@@@@@@@@@@... .@@@@@@@@@@... ..............(See also: wikipedia.org/wiki/Z-order.)
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,"+ ")] .............. .@@@@@@@@@@... .@........@... .@........@... .@......**@**. .@.+++..**@**. .@.+ +..**@**. .@.+++..**@**. .@......**@**. .@........@... .@@@@@@@@@@... ..............
> drawSquares [(0,0,2,"a@"),(1,1,2,"b#"),(2,2,2,"c$"),(3,3,2,"d%")] aa.... abb... .bcc.. ..cdd. ...dd. ...... > drawSquares [(0,0,12," "),(5,5,2,"Xy")] -- " " is two spaces . . . . . XX . XX . . . . . . ............. > drawSquares [(0,5,5,"##"),(50,0,5,"##")] ..................................................#####. ..................................................#...#. ..................................................#...#. ..................................................#...#. ..................................................#####. #####................................................... #...#................................................... #...#................................................... #...#................................................... #####................................................... ........................................................
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 five lines (five bindings) 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 stringRecall 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
ftypes.hs
Slides 111+ 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:
'
), 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 71).
fst
, snd
, or error
.
@
s in your code.)
where
clause, or let
, do
,
or case
expressions.
if-else
.
Violation of a restriction will result in a score of zero for that function.
The final test for ftypes
that the Tester runs is a3/check-ftypes ftypes.hs
. It does
some simple-minded checking for violations of restrictions, but it is not perfect! A common false-positive
is trigged by using a digit in an identifier name, like x1
.
ftypes.hs
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.
The Tester also considers String
to be equivalent to [Char]
If you're not sure whether the type ghci
is reporting is equivalent to the type specified above, just try it with the Tester!
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:
% pwd /home/hbcurry/CSC372/asn3 % a3/turnin ======== contents of a3.20230203.222740.tz ======== -rw-r----- whm/whm 550 2023-02-03 22:27 warmup.hs -rw-rw---- whm/whm 141 2023-02-03 22:27 join.hs -rw-rw---- whm/whm 217 2023-02-03 22:27 rme.hs -rw-rw---- whm/whm 281 2023-02-03 22:27 splits.hs -rw-rw---- whm/whm 272 2023-02-03 22:27 cpfx.hs -rw-rw---- whm/whm 292 2023-02-03 22:27 paired.hs -rw-rw---- whm/whm 2191 2023-02-03 22:27 squares.hs -rw-rw---- whm/whm 2554 2023-02-03 22:27 editstr.hs -rw-rw---- whm/whm 264 2023-02-03 22:27 ftypes.hs -rw-rw---- whm/whm 2184 2023-02-03 17:50 observations.txt ======== running turnin ======== Turning in: a3.20230203.222740.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 52 298 1734 squares.hs 49 220 1210 editstr.hs 12 60 278 ftypes.hs 175 879 4660 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. You might use a3/turnin
whenever you've reached a milestone and
want to save a snapshot 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 372s23
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, CyberDuck, or something similar.
Also, you can email yourself a copy of whatever deliverables you've created like this:
% head -1000 $(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.
head -1000
is used to put a one-line separator between files, like ==> warmup.hs <==
. The -1000
indicates to include the first one-thousand lines of the file, which should be plenty for these problems.
The -s
option for mail
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:
% head -1000 $(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.
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 created 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 between 10-15 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.
Assignments are not take-home tests! We hope you'll make use of Piazza, email, Discord and office hours if problems arise. If you're getting toward the hours I estimate above and don't seem to be close to completing it, or you're simply worried about your progress, email us! Give us a chance to speed you up!
Historically speaking, I've seen a lot of students really struggle with the warmup.hs
functions
but then find themselves able to make steady progress thereafter.