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

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:

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

Examples:

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

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

Hint:

• 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"
["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:

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

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:

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

Examples:

```  Main> snake ["ahoy", "hola", "okay", "yahoo", "obrigado", "haskell"]

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?"
(Question "Still getting wet?"
(Action "Buy a rain coat." Done)
Done))
(Question "Is the sun shining?"
(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
Still getting wet? yes