Introduction to Functional Programming
|DAY: August 24, 2012||TIME: 14:00 -- 18:00||PLACE: V-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
occurs :: Eq a => a -> [a] -> Int
that given an x and a list xs, finds out how often x occurs in the list.
Main> occurs 'a' "bepacepadepa" 3 Main> occurs 11 [2,3,5,7,11,13,7,5] 1 Main> occurs "hej" ["hi","hola","hello","hoi"] 0
2. Accountants are always interested in finding numbers that contain the digit '7'. Implement a function
hasSeven :: [Integer] -> [Integer]
that given a list of numbers, returns exactly those numbers that contain the digit '7'.
Main> hasSeven [3, 13, 27, 771, 674, 301] [27, 771, 674] Main> hasSeven [1, 7] 
3. Consider the following recursive datatype, used to represent arithmetic expressions with addition and multiplication.
data Expr = Num Int | Add Expr Expr | Mul Expr Expr
Now, implement a function
showExpr :: Expr -> String
that displays a given expression as a string, using + for addition and * for multiplication.
Main> showExpr (Add (Num 3) (Mul (Num 7) (Num 8))) (3+(7*8)) Main> showExpr (Num 17) 17
You do not have to minimize the number of parentheses.
4. Write a QuickCheck property that expresses that the length of a list does not change when we reverse it.
prop_Reverse_Length :: [Int] -> Bool ...
5. The well-known UNIX command wc counts the words and lines in a file. Implement a Haskell function:
wc :: FilePath -> IO (Int,Int)
that given a file name, counts the number of words and lines in that file, and returns them as a pair (in that order).
Main> wc "ExamAnswers.hs" -- (a file with 331 words and 96 lines) (331,96) Main> wc "emptyfile.txt" (0,0)
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. In this assignment, you will implement a text processing function called fill that fills paragraphs of text. Your function will take two arguments: (1) an integer indicating the line width of the text, and (2) a list of words. It should then produce a list of lines (the text) containing all the words in the right order, but not exceeding the specified line width.
The type of the function is thus:
fill :: Int -> [String] -> [String] -- width words lines
Here are two examples of its use, demonstrating the effect of line widths 35 and 50 on the same text (taken from the Wikipedia entry on cats):
Main> do s <- readFile "wp_cats.txt"; putStr (unlines (fill 35 (words s))) The cat (Felis catus), also known as the domestic cat or housecat to distinguish it from other felids and felines, is a small, usually furry, domesticated, carnivorous mammal that is valued by humans for its companionship and for its ability to hunt vermin and household pests. Main> do s <- readFile "wp_cats.txt"; putStr (unlines (fill 50 (words s))) The cat (Felis catus), also known as the domestic cat or housecat to distinguish it from other felids and felines, is a small, usually furry, domesticated, carnivorous mammal that is valued by humans for its companionship and for its ability to hunt vermin and household pests.Hint:
7. In this assignment, we will model a file system as a recursive Haskell datatype. Most computer systems, in order to help you organize your files, allow hierarchical storage of files. This means that there are two kinds of files: regular files and directories. A directory can contain several files, some of which in turn can be directories. In this way, we can construct a tree of files and directories.
All this can be modelled in Haskell by means of the following datatype:
data File = File Name | Dir Name [File] type Name = StringWe can see that a file is either a regular file (with just a name), or a directory with a name and a number of files in it. A name is simply a string. We then proceed to model a whole file system as a list of such files.
type FileSystem = [File]A small example of a file system is the following collection of music files and pictures.
example :: FileSystem example = [ Dir "English" [ Dir "Beatles" [ File "she_loves_you.mp3" ] , Dir "Supertramp" [ File "album_art.jpeg" , File "crazy.mp3" , File "school.mp3" ] ] , Dir "Swedish" [ File "du_gamla_du_fria.mp3" , Dir "Kent" [ File "album_art.jpeg" , File "ingenting.mp3" ] , File "tontarna.mp3" ] ]Now, implement a function imprint that takes a file system like the example above, and actually creates (on disk) all files and directories in that file system:
imprint :: FileSystem -> IO ()Any file that is created by imprint will be empty; any directory that is created will be filled with the files and directories specified.
For example, executing imprint example produces the following files and directories:
English/ English/Beatles/ English/Beatles/she_loves_you.mp3 English/Supertramp/ English/Supertramp/album_art.jpeg English/Supertramp/crazy.mp3 English/Supertramp/school.mp3 Swedish/ Swedish/du_gamla_du_fria.mp3 Swedish/Kent/ Swedish/Kent/album_art.jpeg Swedish/Kent/ingenting.mp3 Swedish/Kent/tontarna.mp3You will need to use the following function:
It may come in handy to use the following functions too (but they are not necessary!):
(The above three functions are all available in the standard module System.Directory and free for you to use here.)
Hint A: Use writeFile to create an (empty) file.
Hint B: There are two strategies you can follow. (1) Either you do not use setCurrentDirectory and getCurrentDirectory, in which case you need to keep track of where you are the file system yourself. (2) Or you use setCurrentDirectory and getCurrentDirectory to do this, in which case you should not forget to go back to where you were before after using setCurrentDirectory. Choose!