IN5630

Exercise set 1.

Hi, and welcome to the course Programming Language Implementation and Formalisation. We are excited about the topic, and we hope that you will get the hype as well!

The first week of this course, we will read chapters 3 and 4 of Programming in Haskell by Graham Hutton, which explain types, classes, and functions -- and why they are important. Also, you can take a brief look at chapters 1 and 2 for good measure. Be sure to read 01-getting-started.md, which you can find in the same folder as this document.

Next week, we will take a deeper look at higher order functions and type classes (chapters 7 and 8). Also for good measure, you can take a look at chapters 5 and 6.

In this exercise set, you will find exercises that you can use to test yourself, that you have understood the material.

Credits

This weeks exercise set is based on an exercise set used on the course Advanced Programming, formulated by Ken Friis Larsen and Maya Saietz in 2019.

Quiz.

Have you installed the stack build tool?
In ghci, what is the result of running 3 * 4-5?
In ghci, what does let Name = "Joachim" in length Name evaluate to?

Consider the following program:

f :: Int -> Int -> Int
f m n = m + n

what will the expression:

let g = f 3
    x = 4
    y = 5
in g x

evaluate to?

Consider the function foo given by:
```
foo [        ] = []
foo (x : rest) = [x] : foo rest
```
What is the type of foo ?
Consider the type alias:
```
type Mystery = (Either Ordering Bool, Bool)
```
How many different things can have type Mystery?
Let |_| denote the "cardinality" (the number of inhabitants) of a type. For instance |()| is one and |Bool| is two. Also, consider two arbitrary types a and b. What is the cardinality of (a, b), Either a b and a -> b ?

Fill in the blanks.

Finish the declaration of the function move

type Position = (Int, Int)
data Direction = North | South | East | West

move :: Direction -> Position -> Position
move North (x, y) = (x    , y + 1)
move West  (x, y) = (x - 1, y    )

Declare a function moves with the type
```
moves :: [Direction] -> Position -> Position
```
The function should return the net result of performing all the moves in sequence.
Declare functions for adding and multiplying natural numbers, using the following data type declaration:

   data NaturalNumber = Zero | Successor NaturalNumber
       deriving (Eq, Show, Read, Ord)

The idea is that `Zero` represents the natural number 0, `Successor
Zero` represents the natural number 1, `Successor (Successor Zero)`
represents the natural number 2, and so on.

Your functions should work on the above unary representation _directly_,
not by converting to and from native Haskell integers.

Declare functions nat2int and int2nat to translate natural numbers into Haskell integers and visa versa.
Here is a data type for representing binary search trees with integers stored in the nodes:
```
-- All leaves in left/right subtree are less/greater than node value.
data Tree = Leaf | Node Integer Tree Tree
    deriving (Eq, Show, Read, Ord)
```
Declare a function insert that takes an integer n and a binary search tree t, and returns a new search tree t' with n inserted correctly into t. If n was already present in t, the function should just return t as t'. Insert new elements at the leaves only; do not worry about keeping the tree balanced.

Hint: You may find the standard function compare useful.
Adapt the declaration of Tree to PTree (with constructors PLeaf and PNode), so that it is polymorphic in the data stored in the nodes. What happens to the type of the corresponding insertion function pinsert?
Extend the type Expression (and the function valuate) with operations for multiplication, division, and subtraction
```
data Expression
  = Constant Integer
  | Add      Expression Expression
     deriving (Eq, Show, Read, Ord)

valuate :: Expression -> Integer
valuate (Constant n) = n
valuate (Add  e1 e2) = valuate e1 + valuate e2
```
What happens when you divide by 0? What are the maximum and minimum numeric values that an Expression can evaluate to?
Write a pretty printer function for Expression that inserts as few parentheses as you can manage.

Morse Code

[Rephrased from ruby quiz #121]

Morse code is a way to encode telegraphic messages in a series of long and short sounds or visual signals. During transmission, pauses are used to group letters and words, but in written form the code can be ambiguous.

For example, using the typical dot (.) and dash (-) for a written representation of the code, the word ...---..-....- in Morse code could be an encoding of the names Sofia or Eugenia depending on where you break up the letters:

      ...|---|..-.|..|.-    Sofia
      .|..-|--.|.|-.|..|.-  Eugenia

We will only focus on the alphabet for this quiz to keep things simple. Here are the encodings for each letter:

      A .-            N -.
      B -...          O ---
      C -.-.          P .--.
      D -..           Q --.-
      E .             R .-.
      F ..-.          S ...
      G --.           T -
      H ....          U ..-
      I ..            V ...-
      J .---          W .--
      K -.-           X -..-
      L .-..          Y -.--
      M --            Z --..

Declare a function encode that takes a string (of letters) as argument and translate it to Morse code (as a string).
Declare a function decode that takes a string encoded in morse code as argument and returns a list of all possible translations.

Type classes

Following is an interface for types whose elements can be said to have a size.

class Sizeable t where
  size :: t -> Int

We say that elements of a primitive type like Int all have size one:

instance Sizeable Int where
  size _ = 1

When we want to ascribe a size to aggregate types like lists, we need to take a decision: Should the size of a list be just the length of the list, or is the size of a list the sum of the size of the elements plus the length of the list (plus one). Complete the following two instance declarations (one for each interpretation of what sizeable means)

instance Sizeable [a] where
  ...

instance Sizeable a => Sizeable [a] where
  ...

Note: You cannot have both instance declarations active at the same time.

Make pairs, String, and Tree sizeable.

Challenge of the week (Tic-Tac-Toe)

Open the file TicTacToe.hs, which you can find in the same folder as this document.

Complete the definitions of startState, makeMove, validMove, allValidMoves, and makeTree.

When you make a change, stop and check that the file still compiles. That way, you may know exactly where your error is.
Inspect the function allNodes. What does the functions concatMap, snd, and . (dot) do? Try to write each of these functions yourself.

Observe the difference in running time of

 length (allNodes (makeTree startState))    -- should return 986410

and

      take 3 (allNodes (makeTree startState))

Can you explain that?

Watch Haskell Live episode 1, and make showBoard and readBoard functions for tic-tac-toe boards in a similar style as Rein Henrichs (the Haskell Live creator) does for chess boards.
Implement the minimax algorithm for finding an optimal move in a given game state.

Looking ahead (Monads)

Finish the declaration:
```
data List a = Nil | Cons a (List a)
instance Monad List where
      ...
```
Hint: start by thinking about how the normal list is declared as a monad:
```
instance Monad [] where
      ...
```
Hint 2: Start my defining the functions concat and map for the List type and use these in your declarations.
Rewrite the function findAssociation
```
type AssociationList a = [(String, a)]
findAssociation :: String -> AssociationList a -> a
findAssociation key mapping = head bindings
    where bindings = [value | (key', value) <- mapping, key' == key]
```
so that it returns Nothing rather than producing an error if no binding is found for a key.

Use the re-written findAssociation and the do-notation to write a function that takes an association list and two keys as arguments, looks up the keys, add their values, and return the result.