Haskell slides 1-228 show you all the elements of Haskell you need for this assignment, but the Errors and Debugging sections that follow on slides 229-249 provide useful supplementary information.
As you saw in class, the Larger examples section (250-281) shows examples of building
larger programs using the elements of Haskell that we know. As mentioned in class,
the first "Larger example",
countEO, is misplaced—it should instead be an example in The where clause section.
Assignment 3 had a long preamble that discussed a number of topics. That preamble is not included here but most of it is applicable to this assignment, too.
street.hs
For several semesters one of the larger Haskell problems I posed in 372 was "street".
I later replaced it with "squares", a problem of comparable difficulty that you saw in the
"Assignment 4 Preview", and that is present in this assignment.
In Spring 2018 I made a
recording of live coding of street.hs.
I think that the video provides some examples of how to approach a problem like squares.hs
and also shows some practical techinques for writing and testing functions.
The video is quite long—just over two hours—but you can watch it at up to 2x—espresso mode!
At about 52' and 75' are the start of segments that show the often troublesome leap from "manual"/"hardwired" cases to recursion.
At the start of the video I briefly describe the "streets" problem. If you want to see the full street.hs
write-up, from Spring 2016, it is here.
The video surely could be a lot better but maybe it's worth the time.
Despite itself it definitely "worked" for some students in 2018.
If you watch some or all of it, I welcome your feedback in your observations.txt.
fall22/a4 directory
Just like you did for a3, make a symbolic link for a4.
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.
squares.hs
Write a function drawSquares squares, of type [Square] -> IO () that prints 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—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 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 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 168+), 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 170) 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; 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,"+ ")])
..............
.@@@@@@@@@@...
.@@@@@@@@@@...
.@@@@@@@@@@...
.@@@@@@@*****.
.@@@@@@@*****.
.@@@@@@@*****.
.@@@@@@@*****.
.@@@@@@@*****.
.@@@@@@@@@@...
.@@@@@@@@@@...
..............
(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,"+ ")] .............. .@@@@@@@@@@... .@........@... .@........@... .@......**@**. .@.+++..**@**. .@.+ +..**@**. .@.+++..**@**. .@......**@**. .@........@... .@@@@@@@@@@... ..............
Here are some examples that were not in the preview in the a3 write-up.
> 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 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
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 a4/turnin to submit your work, just like you used a3/turnin on assignment 3.
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, assuming they successfully completed assignment 3.
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, Discord 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!