EXAM
Introduction to Functional Programming
TDA555/DIT440
DAY: October 18, 2010 | 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
(5 small assignments)
|
Part II
(2 larger assignments)
|
Please read the following guidelines carefully: |
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.
Examples:
Main> findIndex 'a' "bepacepa" 3 Main> findIndex 11 [2,3,5,7,11,13] 4 Main> findIndex "hej" ["hej","hi","hola","hello","hoi"] 0
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.
Examples:
Main> extension "tenta.doc" ".doc" Main> extension "Sherlock_Holmes.English.srt" ".srt" Main> extension "www.chalmers.se" ".se"
Hint:
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.
Examples:
Main> eval (And (Val True) (Or (Val False) (Val True))) True Main> eval (Not (And (Val True) (Val False))) True
Hint:
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" ["M","i","ss","i","ss","i","pp","i"] Main> group [2,2,2,1,2,2,5,5,5,5,7,7] [[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)
Hint:
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.
Examples:
Main> yesNoQuestion "Everybody happy?" Everybody happy? yes True Main> yesNoQuestion "To be or not to be?" To be or not to be? hamlet False
(Note that GHCi automatically prints the result of the function ("True" and "False" here) on the last line.)
Hint:
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.
Examples:
Main> snake ["ahoy", "hola", "okay", "yahoo", "obrigado", "haskell"] ["hola","ahoy","yahoo","obrigado","okay"] Main> snake ["george","michael","jackson","eminem"] ["george","eminem","michael"]
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) 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.
Examples:
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.)
Hint: