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: