RE-EXAM
Introduction to Functional Programming
TDA555/DIT440

DAY: August 24, 2012 TIME: 14:00 -- 18:00 PLACE: V-salar

Responsible:
Aids:
Grade:
Koen Lindström Claessen, Datavetenskap
An English (or English-Swedish, or English-X) dictionary
Completing Part I gives a 3 or a G;
Part I and Part II are both needed for a 4, 5, or VG

This exam consists of two parts:

Part I

(5 small assignments)

Give good enough answers for 4 assignments here and you will get a 3 or a G

Part II

(2 larger assignments)

Ignore this part if you are happy with a 3 or a G!

Do Part I and one assignment of your choice here and you will get a 4

Do Part I and both assignments here and you will get a 5 or a VG

Please read the following guidelines carefully:
Answers can be given in Swedish or English
Begin each assignment on a new sheet
Write your number on each sheet
Write clearly; unreadable = wrong!
You can make use of the standard Haskell functions and types given in the attached list (you have to implement other functions yourself if you want to use them)
You do not have to import standard modules in your solutions

Good Luck!

Part I

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.

Examples:

  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'.

Examples:

  Main> hasSeven [3, 13, 27, 771, 674, 301]
  [27, 771, 674]

  Main> hasSeven [1, 7]
  [7]

Hint:

You may use the standard functions show and elem.

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.

Examples:

  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).

Example:

  Main> wc "ExamAnswers.hs"          -- (a file with 331 words and 96 lines)
  (331,96)

  Main> wc "emptyfile.txt"
  (0,0)

Hint:

Use readFile, words, and lines.

Part II

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:

You may use the standard function unwords.

You may implement a helper function split :: Int -> [String] -> ([String],[String]) that splits a list of words into two lists, the first list being just enough words that fit on one line.

When you count line lengths, do not forget to count the spaces between the words.

Think about the special case when a word is too large to even fit on one line all by itself.

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 = 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 "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.mp3

You will need to use the following function:

createDirectory :: FilePath -> IO (), which creates a directory with a given name

It may come in handy to use the following functions too (but they are not necessary!):

getCurrentDirectory :: IO FilePath, which tells you where in a file system you are

setCurrentDirectory :: FilePath -> IO (), which sets the current directory to the specified directory.

(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!