Submission Instructions

Similar to the previous assignment—you must submit a single Haskell file with the following template.

Assignment02.hs
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
module Assignment02 where

-----------------------------------------------------------
-- QUESTION 1


-----------------------------------------------------------
-- QUESTION 2


-----------------------------------------------------------
-- QUESTION 3


-----------------------------------------------------------
-- QUESTION 4

{-
  Write your answer as a comment here.
-}

You can download the template using the button next to the file name. You can also copy any code snippet by hovering over it and clicking the button which appears on the top right.

Warning

Your file name and module name must match the template—any other file or module name will be rejected.

You may not use any imports to solve this lab. If your file contains an import statement, you will get zero marks.

Question 1

Write a function which accepts a list of directions and uses that list to update the position of a point in space. Here is an example of how it should work.

1
2
3
ghci> receiveAndProc
L L L L L U U U D R U  # user input
(-4,3)

Use the following template.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
-- Represents a direction: left, right, up, down.
data Direction = L | R | U | D
  deriving (Show, Read)

-- Represents a position on a grid.
type Position = (Int, Int)

-- This is where the main work should happen.
-- Examples:
--   process [L,L,L,U,U] (0,0) == (-3,2)
--   process [L,R,U,U,D,R] (1,-1) == (2,0)
process :: [Direction] -> Position -> Position
process = undefined

-- This should read a space-separated list of directions
-- and determine the new position of the point (0,0).
receiveAndProc :: IO ()
receiveAndProc = do
  undefined

You will find the following functions useful.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
-- Simple parsing for ‘readable’ types. If Haskell can’t
-- infer what the return type is from context, you will
-- need to provide it like this:
--    read @Int :: String -> Int
--    read @Direction :: String -> Direction
-- The @-symbol is, in this context, a ‘type application’
-- operator — it specialises the type signature to a type
-- that implements the Read typeclass.
read :: Read a => String -> a

-- Splits a string by whitespace.
-- Example:
--   words "1 2\n3" == ["1", "2", "3"]
words :: String -> [String]

-- Applies a function to each of the elements of a list.
-- Example:
--   map (+1) [1,2,3] == [2,3,4]
map :: (a -> b) -> [a] -> [b]

Question 2

Recall the following data type from the lectures.

1
2
3
4
data SimpleIO a
  = Put String (SimpleIO a)
  | Get (String -> SimpleIO a)
  | Return a

Write a function

1
2
exclaim :: SimpleIO a -> SimpleIO a
exclaim = undefined

which takes a SimpleIO computation and appends an exclamation mark to every string that is Put. To test this, you will need the following:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
io :: SimpleIO a -> IO a
io computation =
  case computation of
    Put s rest -> do
      putStrLn s
      io rest

    Get k -> do
      s <- getLine
      io (k s)

    Return a ->
      return a

example :: SimpleIO ()
example =
  Put "Hello" $
  Get $ \name ->
  Put ("My name is " ++ name) $
  Return ()

For example:

1
2
3
4
5
6
7
8
9
ghci> io example
Hello
Conor  # user input
My name is Conor

ghci> io (exclaim example)
Hello!
Conor  # user input
My name is Conor!

Question 3

Traditionally, monads are triples

\[\begin{aligned} \langle M, \; \eta : 1 \to M, \; \mu : M^2 \to M \rangle \end{aligned}\]

You are already familiar with \(\eta\)—that’s return in Haskell. But \(\mu\) is unfamiliar. In Haskell it is called join, and has the type Monad m => m (m a) -> m a. It is possible—and sometimes easier—to define a monad in terms of join instead of (>>=).

Provide a monad instance for the type Arrow r by defining return and join, where join is called arrowJoin, by replacing each undefined with working code. 

1
2
3
4
5
6
7
8
9
newtype Arrow r a = Arrow { apply :: r -> a }
  deriving (Functor, Applicative)

instance Monad (Arrow r) where
  return a = undefined
  m >>= f = arrowJoin (fmap f m)

arrowJoin :: Arrow r (Arrow r a) -> Arrow r a
arrowJoin arrow = undefined

Question 4 (Hard)

Prove that the monad instance you defined in Question 3 satisfies the following monad law: 

1
join . return = id

In practice, this means that, for an arbitrary x :: Arrow r a, you should show the following:

1
arrowJoin (return x) = x

Write this proof as a comment in your Haskell file.