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"])] --------------------------------------------------------------------------------