Due Mon 30 Jan 2006
Now that you have had a basic introduction to the Haskell programming language in the lecture/labs, you will want to get a bit of practice working with the language yourself. There are a lot of features in Haskell, and we will need to learn more about them over the course of the semester, but even with the few you have in hand, you should be able to define some interesting functions. In particular, even though we have just glimpsed how to define functions "explicitly", by means of cases (patter-matching) and recursion, Haskell's higher-order functions and rich Prelude allow you to implement many algorithms just by combining exisiting pieces together.
Below are some problems which you can solve in this fashion, using tools supplied by the Haskell Prelude. In some cases it may help to define some subsidiary functions: in other words, try breaking the problem down into managable pieces and using one function to solve each "piece". I have tried to supply hints which will help you see through to a solution, but feel free to set out in your own direction, as determined by your own perspectives on the problem. I have also included a little mini-glossary of useful functions from the Prelude below. There are other such guides linked from the homepage (and here), but this one has the advantage of high-lighting those functions I think will be most useful for these particular exercises.
Note: unless otherwise indicated, and where it matters, the term "number" below will mean a natural number (i.e., non-negative integer). You should also feel free to make reasonable assumptions about ranges of values (e.g., a date within a month will not be bigger than 2^31 ... ).
Write a function trim0 which will take a string of digits (you may assume that everything in the string is a valid decimal digit) and trims away all the leading zeros ("internal" zeros should be left alone, of course).
Write a function trimSp which will trim the spaces off the front and back of a string. (Here we don't need any special assumptions about which characters are in the string: anything is allowed.)
Given this sdefinition, a value of type Day can only be one of the "new constants" listed above. (And yet these values are probably implemented as integers inside the machine.) You can convert back and forth between these values and Ints using the functions FromEnum and toEnum. (Check the types of these functions using the ":t" command and check what Enum means using the ":i" command; look into the Haskell documentation to see what the "deriving" clause is about.)data Day = Sun | Mon | Tue | Wed | Thu | Fri | Sat deriving (Eq, Ord, Enum, Show)
Write a function whichDay which can be given a Day value representing the first day of a month (e.g., the first day of this month was a Sun, but next month it will be a Wed) and n Int value representing some arbitrary date in that month: it should return a Day value representing the day of the week it will be on that date in the month.
(Hint: the div and mod functions allow you to do arithmetic modulo some fixed period, such as 7 days.)
(Potential snafu: in order to properly use the fromEnum function, Haskell needs to know which type it is "targeting", i.e., to which type it should convert the number. You can "tell" it the type either by giving your function a type explicitly (write the type whichDay :: Day -> Int -> Day on the line above the definition) or by "decorating" an expression with an explicit type (as in succ (toEnum 3 :: Day); try the latter in a Hugs run.)
You might also wish to use the following "integer square root" function. (Although it's not strictly necessary, it can speed things up. And don't worry too much about the "fromIntegeral" function for now.)primes :: Integral a => [a] primes = map head (iterate sieve [2..]) sieve (p:xs) = [ x | x<-xs, x `rem` p /= 0 ]
isqrt :: Integral a => a -> a isqrt = floor . sqrt . fromIntegral
since both these words have 7 letters. Hint: this one is most easily solved using a series of "sub-definitions". The easiest way to do this might be to set up a specific example text as a definition in a file, then work on it interactively, developing new pieces of the definition as you go, so that your file looks something like this:longest "the biggest words here have seven letters" ==> ["biggest", "letters"]
text = "this is some sample text" y = ... text ... f x = ... z = .... f text ...
(I've changed my mind on the hint: you might be able to get a more efficient version using pairs, but it's not the easy way to do it. Look for an easier way.)
(.)
Function composition (usually written as a small, raised
circle in math): the function (f . g) when applied to an
argument x yields (f (g x)); in other words, (f . g) is the
function f "glued together with" the function g as a
"pipeline," so that g is applied, then f in succession to
the result of g.
(.) :: (a -> b) -> (c -> a) -> c -> b
In "(f . g) x", g :: (c -> a) and f :: (a -> b); the
composite function is (f . g) :: (c -> b), so x is of type
c (g's domain), and the result is of type b (f's range).
Example:
((+2) . (^2)) 5
==> (+2) ((^2) 5)
==> (+2) (5 ^ 2)
==> (+2) 25
==> 25 + 2
==> 27
filter
A higher-order function which takes a predicate
argument (i.e., a boolean-valued function) and a list,
and which returns a list of all elements for which the
predicate is True. (More specifically, it respects order
and repetition, so in essence it "deletes" only those
elements for which the predicate returns False.)
filter :: (a -> Bool) -> [a] -> [a]
So in the application "filter p xs", we have
p :: a -> Bool a predicate and xs :: [a] a list; the
result has elements from xs in the same order, with
repetitions, but without any elements for which p
returns False.
Example:
filter even [1, 2, 3, 4, 4, 3, 2, 1]
==> [2, 4, 4, 2]
all
A higher-order predicate which tests if its predicate
argument (i.e., a boolean-valued function) is true of all
the elements in a list.
all :: (a -> Bool) -> [a] -> Bool
So in the application "all p xs", we have p :: a -> Bool
a predicate and xs :: [a] a list; the result tells if
all the elements of xs return True for p.
Example:
all even [2,4..8]
==> all even [2, 4, 6, 8]
==> True
isAlpha
A predicate which tells of a character whether or not it
is an alphabetic character (i.e., whether or not it is a
letter).
isAlpha :: Char -> Bool
Example:
map isAlpha "x #"
==> [isAlpha 'x', isAlpha ' ', isAlpha '#']
==> [True, False, False]
isLower
A predicate which tells of a character whether or not it
is a lowercase alphabetic letter.
isLower :: Char -> Bool
Example:
map isLower "aA@"
==> [isAlpha 'a', isAlpha 'A', isAlpha '@']
==> [True, False, False]
-------------------
zip
A function which pairs up the elements of two lists into
a list of pairs. (Think of a zipper being pulled closed.)
If one of the lists is too short, then its elements are
"cut off" in the result.
zip :: [a] -> [b] -> [(a,b)]
Example:
zip [1..5] "abc"
==> [(1,'a'), (2,'b'), (3,'c')]
words
A function which breaks a String up into a list of
Strings ("words" from the original argument) by
breaking at (and dropping) runs of whitespace.
(Similar in use to a Java StringTokenizer.)
words :: String -> [String]
Example:
words "This is a test"
==> ["This", "is", "a", "test"]
map
A function which applies its function argument (say f)
to every element of its list argument in order to
produce a list of results.
map :: (a -> b) -> [a] -> [b]
Example:
map isLower "aA@"
==> [isAlpha 'a', isAlpha 'A', isAlpha '@']
==> [True, False, False]
maximum
A function on lists of numbers which returns the
maximum element of the list.
maximum :: Ord a => [a] -> a
{don't worry too much about that Ord business; it means
roughly that the elements of the list are, in Java's
terms, Comparable}
Example:
maximum (words "We who are about to fry salute you")
==> maximum ["We","who","are","about","to","fry","salute","you"]
==> "you"
{exercise: what ordering is being used here?}
takeWhile, dropWhile
Two functions which take or drop items from the front of a list, but
only while a given predicate is True. In other words,
this function takes one predicate argument and one
list argument, and returns either a prefix or suffix of the list such
that every element in the prefix meets the test of
the predicate (for takeWhile) or a suffix whiose first element specifically
fails the test.
takeWhile :: (a -> Bool) -> [a] -> [a]
dropWhile :: (a -> Bool) -> [a] -> [a]
Example:
takeWhile (<5) [1..]
==> [1,2,3,4]
dropWhile (<5) [1..10]
==> [5,6,7,8,9,10]