Example Exam
Introduction to Functional Programming
TDA555 / DIT440
HT2010
This exam consists of two parts.
If you want to get a 3 or a G for the exam, you only have to do part I.
If you are interested in getting a 4, 5, or a VG, you also have to do part II.
================================================================================
Part I
You have to complete 4 out of the following 5 assignments to get a 3 or a G.
--------------------------------------------------------------------------------
1. Implement a function
count :: (a->Bool) -> [a] -> Int
that given a function p and a list xs, counts how many elements in xs
that make p True.
Examples:
Main> count even [1,2,3,4,5]
2
Main> count isAlpha "hej hopp"
7
--------------------------------------------------------------------------------
2. Implement a function
names :: String -> [String]
that given a text in the form of a String, finds all names in the text. A name
is a word that starts with a capital letter.
Examples:
Main> names "Kalle hjärta Anna"
["Kalle","Anna"]
Main> names "his name was Thomas but everyone called him Tom"
["Thomas","Tom"]
Hints:
* use the standard functions words and isUpper
--------------------------------------------------------------------------------
data Expr
= Plus Expr Expr
| Minus Expr Expr
| Number Int
3. Implement a function
showExpr :: Expr -> String
that turns an expression of type Expr into a human-readable string. You have to
introduce parentheses where necessary. You do not have to minimize the number
of necessary parentheses.
Examples:
Main> showExpr (Plus (Number 3) (Minus (Number 7) (Number 8)))
(3+(7-8))
Main> showExpr (Number 17)
17
--------------------------------------------------------------------------------
4. Look at the following function definition:
f :: [String] -> String
f [] = ""
f (x:xs)
| length (x:xs) >= 10 == True = "too long"
| otherwise = concat (x:xs)
Please simplify the above function definition as much as possible. Make sure
you do not make any unnecessary case distinctions, overly complicated
expressions, etc.
--------------------------------------------------------------------------------
5. Write a function
sortLinesFile :: FilePath -> IO ()
that, when executed, sorts the lines in a file.
Example:
Main> do s <- readFile "text.txt"; putStr s
bepa
apa
cepa
epa
depa
Main> sortLinesFile "text.txt"
Main> do s <- readFile "text.txt"; putStr s
apa
bepa
cepa
depa
epa
================================================================================
Part II
You do not have to do 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.
--------------------------------------------------------------------------------
A. In this assignment, you will develop a Haskell function that can create an
index for a given piece of text. What is an index? Given a piece of text:
1. Peter The Cat
2.
3. There once was a cat called Peter. He was
4. black and had a long shiny black tail. He liked
5. eating black shiny mice.
An index looks like:
A
a 3 4
and 4
B
black 4 5
C
called 3
cat 1 3
E
eating 5
H
had 4
he 3 4
L
liked 4
long 4
M
mice 5
O
once 3
P
peter 1 3
S
shiny 4 5
T
tail 4
the 1
there 3
W
was 3
In other words, each word in the text occurs once in the index, together with
a series of line numbers the word occurs on. In order to make searching easier,
the index contains letters A, B, C, E, ... before each block of words that
starts with that word.
Implement a function
index :: [String] -> [String]
that given a text (represented as a list of lines from the text), produces
a text containing the index (again, represented as a list of lines). Your
function should produce the index as above for the text as above:
Main> index ["Peter The Cat","","There once was...
["A","a 3 4","and 4","B","black 4 5","C","called 3",...
Hint: You may choose to implement the following functions:
-- find all words in a string, taking care of commas, periods, etc.
-- example: words' "Apa, bepa. !Cepa!" == ["apa","bepa","cepa"]
words' :: String -> [String]
-- gathering information about elements in a tuple
-- example: gather [("hej",1),("hi",3),("hej",2)] ==
-- [("hej",[1,2]),("hi",[3])]
gather :: (Ord a, Ord b) => [(a,b)] -> [(a,[b])]
-- adding help-letters whenever words start with a new letter
-- example: indexLetters ["apa","aardvark","bepa","zebra"] ==
-- ["A","apa","aardvark","B","bepa","Z","zebra"]
indexLetters :: [String] -> [String]
But you do not have to!
--------------------------------------------------------------------------------
B. 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 = String
We 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 "en_timme_en_minut.mp3"
, File "ingenting.mp3" ]
]
]
Lastly, the concept of path (sökväg) is a useful one when talking about file
systems. A path indicates a particular point in a file system (which itself is
a file system again). For example, if we enter the directory "English" in the
above file system, and subsequently enter the directory "Supertramp", our path
is "English/Supertramp".
We represent paths by the following Haskell datatype.
type Path = [Name]
So, the path "English/Supertramp" has the Haskell representation
["English","Supertramp"].
Implement a function
findFiles :: (Name -> Bool) -> FileSystem -> [(Name,Path)]
that, given a function p and a file system, produces a list of all regular
files in the file system that make the function p True. Each entry in the list
contains the name of the regular file, and the path leading to that file.
Example:
Main> findFiles (".jpeg" `isSuffixOf`) example
[("album_art.jpeg",["English","Supertramp"]),("album_art.jpeg",["Swedish","Kent"])]
--------------------------------------------------------------------------------