Introduction to Functional Programming
|DAY: January 14, 2011||TIME: 8:30 -- 12:30||PLACE: M-salar|
Koen Lindström Claessen, Datavetenskap|
An English (or English-Swedish, or English-X) dictionary
Completing Part I gives a 3 or a G;
(5 small assignments)
(2 larger assignments)
|Please read the following guidelines carefully:|
You have to complete 4 out of the following 5 assignments to get a pass on the exam.
1. Implement a function
ordered :: Ord a => [a] -> Bool
that given a list of elements, checks if the list is in sorted order.
Main> ordered [4,8,15,16,23,42] True Main> ordered ["apa","bepa","cepa","xepa"] True Main> ordered  True Main> ordered ["hej","hi","hola","hello","hoi"] False
2. Implement a function
split :: String -> (String,String)
that given a string that contains one forward slash character ('/'), produces the part of the string before the '/' and the part of the string after the '/'.
You may assume that the string contains exactly one '/'. (Your function may do whatever it wants if the string contains no forward slashes or more than one forward slash.)
Make sure that the forward slash character does not appear in any of the results anymore!
Main> split "14/1" ("14","1") Main> split "home/koen" ("home","koen") Main> split "/slashdot" ("","slashdot")
3. Consider the following recursive datatype, used to store integers in a tree shape.
data Store = Empty | Join Int Store Store
Now, implement a function
size :: Store -> Int
that counts the number of integer elements in the tree.
Main> size Empty 0 Main> size (Join 7 Empty (Join 3 Empty Empty)) 2
4. Consider the function
nub :: Eq a => [a] -> [a]
It removes all elements from the list that occur more than once.
Main> nub "Mississippi" "Misp" Main> nub [5,4,5,1,2] [5,4,1,2]
Do not implement this function! Instead, define a QuickCheck property about nub that expresses that the resulting list does not contain any duplicate elements.
5. Write a function
copyFile :: FilePath -> FilePath -> IO ()
which takes two file names, and copies the contents of the first file to the second file.
Main> readFile "apa.txt" "abracadabra" Main> copyFile "apa.txt" "bepa.txt" Main> readFile "bepa.txt" "abracadabra"
Do not work on this part if you only want to get a 3 or a G!
If you want to get a 4, you have to do Part I, plus one of the following assignments.
If you want to get a 5 or a VG, you have to do Part I, plus both of the following assignments.
6. A "word snake" is a sequence of words where each word starts with the letter that the previous word ends with. An example is:
hola ahoy yahoo obrigado okay
This is a word snake because "hola" ends with an "a" and "ahoy" starts with an "a"; "ahoy" ends with a "y" and "yahoo" starts with a "y"; etc.
One way to represent a word snake in Haskell is by a list of Strings:
type Snake = [String]
Implement a function:
snake :: [String] -> Snake
that, given a list of words, finds the longest word snake that can be built from using these words. ("Longest" refers to counting the number of words in a word snake.) Each word in the list can only be used once (and some words might never be used).
You may assume that (1) all given words are non-empty, and that (2) no word occurs more than once in the word-list.
Main> snake ["ahoy", "hola", "okay", "yahoo", "obrigado", "haskell"] ["hola","ahoy","yahoo","obrigado","okay"] Main> snake ["george","michael","jackson","eminem"] ["george","eminem","michael"]
You do not have to optimize your function for efficiency.
Hints: You may benefit from defining the following functions:
-- build the longest snake that starts with a given letter snakeWith :: Char -> [String] -> Snake -- given a list of snakes, find the longest snake in the list longest :: [Snake] -> Snake
But you do not have to define or use these.
7. The HyperText Markup Language, better known as HTML, is a language for describing documents. All webpages are written using HTML.
Documents written in HTML have a structure that is determined by the use of tags. We can enclose a certain part of our document within certain tags, in order to indicate this structure. To enclose a part of a document in tags, we use matching open tags and close tags. For example:(In reality, tags contain more information than just the tag name (such as B, EM, P, etc.), but for simplicity we do not deal with that here.)
Here is an example of HTML code:
Welcome to my website!<P><B>My hobbies are <EM>Haskell</EM> programming and playing <EM>Myst</EM>.</B></P><P>Thanks for visiting! <EM>email@example.com</EM></P>And here is what it would look like in a browser:
Welcome to my website!We can represent HTML documents in Haskell in the following way. First, we realize that a document consists of a bunch of document parts.
My hobbies are Haskell programming and playing Myst.
Thanks for visiting! firstname.lastname@example.org
type Doc = [DocPart]
There are two kinds of document parts: (1) A piece of text, (2) A whole document enclosed in a certain kind of tag.
data DocPart = Text String | Tag String Doc
The example piece of HTML above can be represented by the following Haskell expression:
annasSida :: Doc annasSida = [ Text "Welcome to my website!" , Tag "P" [ Tag "B" [ Text "My hobbies are " , Tag "EM" [ Text "Haskell" ] , Text " programming and playing " , Tag "EM" [ Text "Myst" ] , Text "." ] ] , Tag "P" [ Text "Thanks for visiting! " , Tag "EM" [ Text "email@example.com" ] ] ]Sometimes, a web site looks strange in a certain browser, but fine in another browser. This is because not all browsers understand all tags in the same way. Sometimes a browser gets so confused by a certain tag, that it is better just to remove that tag from a document completely. When doing this, one should not also remove the part of the document that is enclosed within these tags.
Define a function:
removeTag :: String -> Doc -> Docthat removes the given tag from a given document, but keeps the information enclosed in those tags.
Main> showDoc (removeTag "B" (removeTag "EM" annasSida)) "Welcome to my website!<P>My hobbies are Haskell programming and playing Myst.</P><P>Thanks for visiting! firstname.lastname@example.org</P>"
(In the above example, we use the function:
showDoc :: Doc -> Stringthat produces a String containing the actual HTML code of the given document. For example, if the argument to showDoc is annasSida, then the result should be the HTML code as a String shown earlier. So, you do not have to implement showDoc.)