CSCC24 2020 Summer – Assignment 2
Due: Sunday, July 26, midnight
This assignment is worth 10% of the course grade.
In this assignment, a domain-specific monadic type class is given, i.e., there are domain-specific methods, along with the usual Monad, Applicative, and Functor methods as connectives. You will work on both sides of the fence:
• You will implement a program in the domain. It uses only the methods, and so it is poly- morphic in the type class. It can be instantied different ways for different purposes.
• You will implement an instance of this monad class. (This means a model or representation semantics.)
As usual, you should also aim for reasonably efficient algorithms and reasonably organized, comprehensible code.
The Pinch Game
The Pinch Game is a solitaire game played on an array of integers; the array indexes are 1-based to stay intuitive for most people. Example: [3, 2, 0, 1].
At each turn, you can pinch up at a position (index) i. Intuitively, pinching up increases the cell at i but also affects neighbouring cells to a lesser degree. Precisely, Provided that i is a valid position, the cell at i goes up by 2, the cell at i−1 (if it exists) goes up by 1, and the cell at i+1 (if it exists) goes up by 1.
You can instead pinch down; then the affected cells go down instead. Example game play: Starting from [3, 2, 0, 1]:
1. Pinch up at 3: [3,3,2,2]
2. Pinch down at 1: [1, 2, 2, 2] 3. Pinch down at 2: [0, 0, 1, 2] 4. Pinch down at 4: [0, 0, 0, 0]
The game ends when the whole array is 0s, like after that last turn. (Corner case: If the game begins with all 0s, there are no turns, the game ends immediately.)
Question 1: Game Server (10 marks)
This type class is defined for the method that the game server uses to converse with the player:
class Monad m => MonadPinchSim m where
askPinch :: Msg -> Array Int Integer -> m (Int, Direction)
data Msg = NoMsg | OKMsg | BadPositionMsg data Direction = Down | Up
1
The game server calls askPinch to give a message and the current array to the player. When this method returns, the return value is the pinch position and direction chosen by the player. Important: The game logic is not in this method; the game logic is in the following game server you implement:
Implement the game server
pinchServer :: MonadPinchSim m => Array Int Integer -> m ()
The parameter is the initial array, e.g., listArray (1,4) [3,2,0,1]. At every turn, the game server should call askPinch to give a message (details below) and the current array to the player, then examine the player’s pinch instruction, then replace the array accordingly. Repeat until the array is all 0s, then end with answer ().
The message tells the player whether the preceding pinch position is valid:
• At the first turn, the message should be NoMsg, since there is no preceding pinching.
• Whenever a pinch position is valid, the message in the next turn should be OKMsg.
• Whenever a pinch position is invalid, the message in the next turn should be BadPositionMsg. Also, the array should be unchanged.
You can test your game server by playIO from PinchApp.hs, e.g., playIO (pinchServer (listArray (1,4) [3,2,0,1]))
This instantiates askPinch to actually converse with you via stdio.
Question 2: Game Tree (5 marks)
Pinch Game server behaviours (correct or incorrect) can be represented in a data form:
data PinchTrace a
= Pure a
| Step Msg (Array Int Integer) (Int -> Direction -> PinchTrace a)
You can think of this a tree of execution steps. Pure is for leaves. Step is for those steps when a server gives a message and an array, and waits for player’s pinch instruction before it can decide what to do next.
Why is it a tree? Because a function of type Int -> Direction -> PinchTrace a says that, for each pinch position and direction, you have a child subtree.
This PinchTrace type can be made an instance of both Monad and MonadPinchSim. Implement them. Some hints:
• Pure a >>= k can only be one thing, dictated by a monad law.
• One explanation for Step msg arr next >>= k: Can it become a Pure? No, so it must become a Step. What should be the message and array fields? How should the function field use both next and k in the correct order?
• Another explanation for Step msg arr next >>= k: Step msg arr next is a tree, >>= wants to extend this tree (at the leaves) by k. Can you help it using recursion?
2
• For askPinch, it has to be a Step. What should be the message and array fields? The function field will be anti-climatic.
You can test by your game server and playTrace from PinchApp.hs. playTrace (pinchServer (listArray (1,4) [3,2,0,1]))
It works by instantiating your game server to the PinchTrace type, then for each Step actually converses with you via stdio. So it is walking down one path in the tree, using your input to choose the path.
Since PinchTrace is data, we could also write autotesting, using pattern matching to check that we get Step when we expect it, and check messages and arrays. This is illustrated in mytest from PinchApp.hs.
End of questions.
3