Introduction to Functional Programming

DAY: October 18, 2010 TIME: 8:30 -- 12:30 PLACE: M-salar




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

      findIndex :: Eq a => a -> [a] -> Int

    that given an x and a list xs, finds out at what position x occurs in the list. We start counting positions at 0. If there are multiple positions, the function findIndex always produces the first position x is at.


      Main> findIndex 'a' "bepacepa"
      Main> findIndex 11 [2,3,5,7,11,13]
      Main> findIndex "hej" ["hej","hi","hola","hello","hoi"]

    The function may assume that x actually occurs in the list. (So, you may do whatever you want if x does not occur in the list.)

    2. Implement a function

      extension :: String -> String

    that given a file name, produces the file extension. The extension consists of the last dot (".") occurring in the file name, plus all characters following that dot.

    If there is no dot in the filename, you may decide yourself what you do.

    If there is more than one dot in the filename, the extension starts at the last dot.


      Main> extension "tenta.doc"
      Main> extension "Sherlock_Holmes.English.srt"
      Main> extension "www.chalmers.se"


  • use the standard functions reverse and takeWhile

    3. Consider the following datatype, modelling logical formulas in Haskell.

      data Form
        = And Form Form
        | Or Form Form
        | Not Form
        | Val Bool

    Now, implement a function

      eval :: Form -> Bool

    that evaluates a given formula to its value, a Boolean.


      Main> eval (And (Val True) (Or (Val False) (Val True)))
      Main> eval (Not (And (Val True) (Val False)))


  • Use the standard functions (&&), (||), and not.

    4. Consider the standard Haskell function

      group :: Eq a => [a] -> [[a]]

    It takes a list and chops it up into "groups", where each group only has equal elements.

    For example:

      Main> group "Mississippi"
      Main> group [2,2,2,1,2,2,5,5,5,5,7,7]

    Do not implement this function! Instead, define two QuickCheck properties about group that express the following:

    (a) for each group in the result, all elements are equal

    (b) concatenating (glueing together) all groups in the result gives us back the original list (the order of elements is preserved)


  • Use the functions nub and concat

    5. Write a function

      yesNoQuestion :: String -> IO Bool

    which takes a question (a String) as an argument, prints it on the screen, and waits for the user to type an answer. If the answer is "yes", the result is True; any other answer produces the result False.


      Main> yesNoQuestion "Everybody happy?"
      Everybody happy? yes
      Main> yesNoQuestion "To be or not to be?"
      To be or not to be? hamlet

    (Note that GHCi automatically prints the result of the function ("True" and "False" here) on the last line.)


  • Use the function getLine to get the user input

    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. A "word snake" is a sequence of words where each word starts with the letter that the previous word ends with. An example is:

      hola  ahoy  yahoo  obrigado  okay

    This is a word snake because "hola" ends with an "a" and "ahoy" starts with an "a"; "ahoy" ends with a "y" and "yahoo" starts with a "y"; etc.

    One way to represent a word snake in Haskell is by a list of Strings:

      type Snake = [String]

    Implement a function:

      snake :: [String] -> Snake

    that, given a list of words, finds the longest word snake that can be built from using these words. Each word in the list can only be used once (and some words might never be used).

    You may assume that (1) all given words are non-empty, and that (2) no word occurs more than once in the word-list.


      Main> snake ["ahoy", "hola", "okay", "yahoo", "obrigado", "haskell"]
      Main> snake ["george","michael","jackson","eminem"]

    You do not have to optimize your function for efficiency.

    Hints: You may benefit from defining the following functions:

      -- build the longest snake that starts with a given letter
      snakeWith :: Char -> [String] -> Snake
      -- given a list of snakes, find the longest snake in the list
      longest :: [Snake] -> Snake

    But you do not have to define or use these.

    7. Consider the following recursive datatype modelling so-called action diagrams:

      data Diagram
        = Question String Diagram Diagram
        | Action String Diagram
        | Done

    An example of an action diagram is presented in the following figure:

    We can represent this diagram using the above datatype as follows:

      example :: Diagram
      example =
        Question "Is it raining?"
          (Action "Buy an umbrella."
            (Question "Still getting wet?"
               (Action "Buy a rain coat." Done)
          (Question "Is the sun shining?"
            (Action "Buy sun glasses."
              (Action "Go to the beach." Done))
            (Action "Stay at home." Done))

    Implement a function

      follow :: Diagram -> IO [Action]

    that, given an action diagram, asks the user the relevant questions in the diagram, and follows the diagram depending on the answers. Whenever there is an action that needs to be performed, it is printed on the screen. When the function finishes, it also produces a list of all actions that were supposed to be taken.


      Main> follow example
      Is it raining? yes
      Buy an umbrella.
      Still getting wet? yes
      Buy a rain coat.
      ["Buy an umbrella.","Buy a rain coat."]
      Main> follow example
      Is it raining? no
      Is the sun shining? yes
      Buy sun glasses.
      Go to the beach.
      ["Buy sun glasses.","Go to the beach."]

    (Note that GHCi automatically prints the result of the function (the list of actions) on the last line.)


  • You may use the function yesNoQuestion from Part I, assignment 5.