EXAM
Introduction to Functional Programming
TDA555/DIT440


DAY: October 17, 2011 TIME: 8:30 -- 12:30 PLACE: M-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

      removeIndex :: Int -> [a] -> [a]
    

    that given an index i and a list xs, removes the element that is at index i. We start counting positions at 0.

    Examples:

      Main> removeIndex 3 "bepacepa"
      "bepcepa"
    
      Main> removeIndex 0 [2,3,17,4]
      [3,17,4]
    

    The function may assume that the list contains enough elements for the index i to be removed. (So, you may do whatever you want if the index i is too small or too large.)

    Hint:

  • You may use the standard functions take and drop


    2. Implement a function

      emails :: String -> [String]
    

    that given a text (as a string), returns a list with all e-mail addresses in that text. An e-mail address is a word with exactly one occurrence of the @-sign.

    Examples:

      Main> emails "kalle@apa.com and anna@bepa.org are my friends"
      ["kalle@apa.com", "anna@bepa.org"]
    
      Main> emails "koen@chalmers@se is not right, mister can@not.spell.se"
      ["can@not.spell.se"]
    

    Hint:

  • You may use the standard functions words and filter. You do not have to do anything special with other lexical signs such as periods and commas.


    3. Consider the following recursive datatype, used to represent arithmetic expressions with variables (denoted as X).

      data Expr
        = Num Int
        | Add Expr Expr
        | X
    

    Now, implement a function

      numVars :: Expr -> Int
    

    that counts the number of variable occurrences in the tree.

    Examples:

      Main> numVars (Num 3)
      0
    
      Main> numVars X
      1
    
      Main> numVars (Add X (Add (Num 13) X))
      2
    


    4. Anna is writing a QuickCheck property involving the functions reverse and ++. She has written:

      prop_Reverse_Append :: [Int] -> [Int] -> Bool
      prop_Reverse_Append xs ys =
        reverse (xs ++ ys) == ...
    

    But then she got stuck.

    Can you help Anna by giving a Haskell expression you can write instead of the ... which makes the property correct? (It should be something different than the left-hand side of course.)


    5. Write a function

      palindrome :: IO ()
    

    which asks the user to type in a word, and then says if that word is a palindrome or not. (A palindrome is a word that is spelled the same, regardless of reading it forwards or backwards. Examples of palindromes are "rotator" and "level"; reading them backwards yield the same word again.)

    Examples:

      Main> palindrome
      Type in a word> racecar
      racecar is a palindrome!
    
      Main> palindrome
      Type in a word> haskell
      haskell is not a palindrome!
    
      Main> palindrome
      Type in a word> apa
      apa is a palindrome!
    

    Hint:

  • Use getLine and reverse.



    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. The HyperText Markup Language, better known as HTML, is a language for describing documents. All webpages are written using HTML.

    Documents written in HTML have a structure that is determined by the use of tags. We can enclose a certain part of our document within certain tags, in order to indicate this structure. To enclose a part of a document in tags, we use matching open tags and close tags. For example:

  • Text enclosed in boldface tags <B> ... </B> indicates that the text should be in boldface. Here, <B> is the open tag, and </B> is the corresponding close tag.
  • Text enclosed in emphasize tags <EM> ... </EM> indicates that the text should be emphasized (often using italics).
  • Text enclosed in paragraph tags <P> ... </P> indicates that the text forms a paragraph (often by having an empty line before and after).
  • (In reality, tags contain more information than just the tag name (such as B, EM, P, etc.), but for simplicity we do not deal with that here.)

    Here is an example of HTML code:

    Welcome to my website!<P><B>My hobbies are <EM>Haskell</EM> programming and playing <EM>Myst</EM>.</B></P><P>Thanks for visiting! <EM>anna@gmail.com</EM></P>
    And here is what it would look like in a browser:
    Welcome to my website!

    My hobbies are Haskell programming and playing Myst.

    Thanks for visiting! anna@gmail.com

    We can represent HTML documents in Haskell in the following way. First, we realize that a document consists of a bunch of document parts.

      type Doc = [DocPart]
    

    There are two kinds of document parts: (1) A piece of text, (2) A whole document enclosed in a certain kind of tag.

      data DocPart
        = Text String
        | Tag String Doc
    

    The example piece of HTML above can be represented by the following Haskell expression:

      annasSida :: Doc
      annasSida =
        [ Text "Welcome to my website!"
        , Tag "P" [ Tag "B" [ Text "My hobbies are "
                            , Tag "EM" [ Text "Haskell" ]
                            , Text " programming and playing "
                            , Tag "EM" [ Text "Myst" ]
                            , Text "."
                            ] ]
        , Tag "P" [ Text "Thanks for visiting! "
                  , Tag "EM" [ Text "anna@gmail.com" ]
                  ]
        ]
    

    Sometimes, a web site looks strange in a certain browser, but fine in another browser. This is because not all browsers understand all tags in the same way. Sometimes a browser gets so confused by a certain tag, that it is better just to remove that tag from a document completely. When doing this, one should not also remove the part of the document that is enclosed within these tags.

    Define a function:

      removeTag :: String -> Doc -> Doc
    
    that removes the given tag from a given document, but keeps the information enclosed in those tags.

    Example:

      Main> showDoc (removeTag "B" (removeTag "EM" annasSida))
      "Welcome to my website!<P>My hobbies are Haskell programming and 
      playing Myst.</P><P>Thanks for visiting! anna@gmail.com</P>"
    

    (In the above example, we use the function:

      showDoc :: Doc -> String
    

    that produces a String containing the actual HTML code of the given document. For example, if the argument to showDoc is annasSida, then the result should be the HTML code as a String shown earlier. So, you do not have to implement showDoc.)