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!