Here are some more exercises: the simpler ones are pretty straightforward, but the later ones will involve some recursion. You are encouraged to use the “template style” or even folds to get things going, especially for the recursive ones. Also be sure to check out the page with the example-based approach to code development for ideas about how to proceed.
Here’s a simple little warm-up, based on text ideas, but requiring a type definition. Let’s define a two-valued type, similar to Booleans, but with the meaning of distinguishing between vowels, consonants and other characters:
data Cat = Vow | Con | Other deriving (Show, Eq)
(Include this definition near the top of your file.)
The interpretation of Cat
is “character category”
and it allows us to distinguish between the vowel and consonant categories
(or “other” characters) in a typical Haskell-y abbreviated fashion.
(Let’s agree to consider 'y'
a vowel by default, just because.)
You should define a classifying or “categorizing” function on
values of type Char
which takes a character argument and tells
whether it is a vowel, consonant or neither; i.e., you should write a function
cat :: Char -> Cat
. (This shoudn’t be too hard, but will
require working with the new datatype.)
OK, now for the actual working part of the exercise: define a function which
will take a piece of text (i.e., a String
) and, based on a
Cat
argument value, replace every character of the type in
the string with an asterisk ('*'
); the non-selected categories
of characters should remain unchanged.
So you’ll write a function replace
that behaves as follows:
replace :: Cat -> String -> String
Hugs> replace Vow "kitty cat"
"k*tt* c*t"
Hugs> replace Con "hot diggity dog"
"*o* *i**i*y *o*"
(This part shouldn’t be too hard either, but this is just a warm-up exercise, after all.)
Note that Other
is a possible argument
to the function, so that vowels and consonants might survive unchanged, but
spaces, punctuation, tabs, etc., would be converted to asterisks.
Let’s do some math with non-integer numbers. Specifically, we’ll work with circles in a geometric plane, conceived in terms of cartesian co-ordinates (you know, the old “(x,y)” routine). You can write these values into Haskell by just using decimal points in your numbers.
More specifically, let’s work with circles represented in terms of
three numbers, an x-coordinate, a y-coordinate (these two represent the
center of the circle), and a radius (the distance from the center of the circle
to it’s “edge”, i.e., the circle itself). We can define a
circle datatype as follows, where the constructor Circle
will
build a circle representation from three floating-point numbers:
data Circle = Circle Float Float Float deriving Show
(Again, just add this line to your lab file.)
Now for the fun part: write a function overlap
which will take
two Circle
s as argument and tell (as a Bool
result)
whether they overlap or not. Recall that two circles overlap if the distance
between them is less than the sum of their radii. (The distance between two
points, as you’ll recall, is the square root of the sum of the squares
of the differences between their respective coordinates.) Note that Haskell
has a sqrt
function to do the square roots for you (I pronounce it
“squirt”, but maybe that’s just me ...).
overlap :: Circle -> Circle -> Bool
Hugs> overlap (Circle 0.0 0.0 3.0) (Circle 2.0 2.0 1.0)
True
Hugs> overlap (Circle 1.0 1.0 1.0) (Circle 5.0 5.0 1.0)
False
Clarification: You should count only one overlap for each pair of distinct circles that overlap. In other words, don’t count circles overlapping with themselves, but also don’t count two distinct circles overlapping with each other twice, just count them once.
perms
: given a list xs
,
it should produce the list of all permutations of the xs
,
i.e., a list of all lists which are a re-ordering of the elements in
xs
. If there are duplicate elements, they should
be considered effectively different: in other words, what matters is that you
permute in some sense the positions in the list, not the specific elements
(although of course your answer lists will contain the original elements).
perms :: [a] -> [[a]]
Hugs> perms "abc"
["abc","bac","bca","acb","cab","cba"]
Hugs> perms "aba"
["aba","baa","baa","aab","aab","aba"] -- note treatment of duplicates
combos
: when given two lists xs
and ys
,
it should produce a list of all combinations (as pairs) of the
form (x,y)
, such that x
comes from the list xs
and
y
from the list ys
.
(In particular, make sure that duplicate elements in the lists yield duplicate
elements in the results.)
combos :: [a] -> [b] -> [(a,b)]
Hugs> combos [1..3] "abcd"
[(1,'a'),(1,'b'),(1,'c'),(1,'d'),(2,'a'),(2,'b'),(2,'c'),(2,'d'),(3,'a'),(3,'b'),(3,'c'),(3,'d')]
Given your definition of the overlap
and combos
functions,
you should be able to write a function that takes a list of circles and
returns the number of distinct pairwise overlaps between circles in the list.
(Just to be sure, we won’t consider a circle to overlap with itself, so
be sure to exclude that possibility somehow in the count.)
overlaps :: [Circle] -> Int
(I’ll supply some sample test data in a separate file over the weekend.)
NEW!! OK, here is some test data, not as a separate file, but just as a paste-able block:
circs1 = [ Circle 2.0 5.0 1.0, Circle 13.0 7.0 1.0, Circle 7.0 4.0 3.0, Circle 4.0 7.0 2.0, Circle 10.0 7.0 2.0 ] {- 4 overlaps -} circs2 = [ Circle 5.0 5.0 1.0, Circle 5.0 5.0 2.0, Circle 5.0 5.0 3.0 ] {- 3 overlaps -} circs3 = [ Circle 6.5 8.0 2.0, Circle 3.0 7.0 1.0, Circle 3.0 3.0 2.0, Circle 6.5 5.5 1.0, Circle 3.0 5.5 1.0, Circle 6.5 3.0 2.0 ] {- 5 overlaps -}
[ [ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ] ]
The transpose of a matrix is a new matrix where the roles of the columns and rows
are exchanged; for a list of lists, this means in some sense that we turn the list of
lists "inside out. So the transpose of the example above is:
[ [ 1, 4, 7 ],
[ 2, 5, 8 ],
[ 3, 6, 9 ] ]
Write a function called trans
that will transpose a lists of lists as above.
Note: if there are "short" lists within the outer list, you could just trim all the lists in
the result to match. (Can you think of other reasonable behaviors?)
A simple "encryption" mechanism used in Usenet newsgroups, back in the 1900's, was called ROT13. It didn't actually encrypt text (it's too easily inverted), but rather was used to hide text from being immediately read. This feature was useful for delaying punch lines to jokes, or movie spoilers, for example, or as a simple way to block potentially objectionable material (one had to overtly "decrypt" the text, thus implicitly agreeing not to be offended).
(See Wikipedia's entry on ROT13 for more
information, history and trivia. Furrfu! Fnir zr sebz gur abbof!)
The idea behind the ROT13 technique is simple: every alphabetic character in the message
is "rotated" 13 letters forward through the alphabet, wrapping back around from the end to
the beginning when necessary. (NB: all non-alphabetic symbols are preserved unchanged.)
Note that upper-and lower-case letters must be treated a bit differently, since they lie
in different alphabetic ranges. (In Haskell, you can achieve the rotation by first converting
characters to numbers in the ASCII code via the ord
function in the
Char
module; then you will need some arithmetic, and probably the mod
function, to hep the rotation. But there are other approaches ... .)
Define a rot
function that takes a number n
(usually 13) and a
string, and returns a new string to which the technique has been applied. By way of example:
Hugs> rot 13 "This is a message; it is a test, just a test."
"Guvf vf n zrffntr; vg vf n grfg, whfg n grfg."
(Of course, 13 was used in the ROT13 technique since it allowed one to "toggle" between obscured and plain text by simply applying the function again; in other words, it was self-inverse with n=13.)