Define the Functor, Applicative, and Monad type classes, assuming that they are not predefined. Also declare that Maybe and [] are instances of these type classes.
In Haskell, the predefined Either type has this definition:
data Either a b = Left a | Right b
Sometimes we use an Either to represent a value that is either correct or is an error. By convention, Right holds a correct value and Left holds an error. You can think of Either as being a variant of Maybe in which Nothing can hold a value such as an error message.
Declare that Either is a member of the Functor, Applicative, and Monad type classes. If necessary, perform experiments to determine how it should behave.
Define a type Rand a representing a
randomized computation that returns a value of type a. Rand
should be a monad. Provide these functions:
randomInt lo hi produces a random integer in the
given range from lo to hi, inclusive.coin_flip :: Rand Bool
coin_flip = do
i <- randomInt 1 2
return (i == 2)
count :: Rand Int
count = do
b <- coin_flip
if b then return 1 else do
c <- count
return (c + 1)
> run count
2
> run count
1
> run count
3Define a type Logger a
representing a computation which returns a value of type a, and may
also produce a series of strings as it does so. We can think of
these strings as logging output that the computation has generated.
Logger should be a monad. Provide these functions:
Define a type State a representing a
computation that returns a value of type a, and may get and set named
integer values as it does so. It is an error to get any value before
it has been set. State should be a monad. Provide these functions:
For example:
loop :: State Int
loop = do
a <- get "a"
b <- get "b"
if b == 0 then return a
else do
set "a" b
set "b" (a `mod` b)
loop
gcd :: Int -> Int -> State Int
gcd a b = do
set "a" a
set "b" b
loop
> run (gcd 24 18)
6Fox and Hounds is a two-player game played on the black squares of an 8 x 8 chessboard:
One player controls a single fox, and the other controls four hounds. On the fox's turn, he can move one square in any direction diagonally. On the hounds' turn, one hound can move one square diagonally forward. The fox moves first. If the fox reaches the last row, he wins. If any player is ever unable to move, they lose.
a) Create a type Game representing
the state of this game. Also create a value start :: Game
representing the initial state of the game.
b) Write a function show_game :: Game →
String that produces a visual representation of the board:
> putStr (show_game start) H H H H . . . . . . . . . . . . . . . . . . . . . . . . F . . . >
c) Create a type Move representing a move in this game.
d) Write a function possible :: Game →
[Move] that produces a list of all possible moves for any
state.
e) Write a function move :: Game → Move →
Game that applies a valid move to a game state, producing a
new state.
f) Write an interactive program that allows a player at the terminal to play as the fox versus a computer player, who controls the hounds. For the computer player, use a dummy strategy that just chooses the first possible move. The player should enter their move as one of the string "ul", "ur", "dl" or "dr", where e.g. "ul" means to move up and left. If the game ends, print "You won!" or "You lost!" and exit.
For example:
> play H H H H . . . . . . . . . . . . . . . . . . . . . . . . F . . . Your move? ur . H H H H . . . . . . . . . . . . . . . . . . . F . . . . . . . Your move? ul . H H H . . . . H . . . . . . . . . . . F . . . . . . . . . . . Your move?
g) Modify the computer player to be stronger.
Consider the game of Rock, Paper, Scissors. Two players choose their moves simultaneously. Paper beats rock; rock beats scissors; scissors beats papers. Suppose that two players will play a series of games. A strategy for this game is a function which chooses a move, given all moves that the opponent has played before:
data Move = Rock | Paper | Scissors type Strategy = [Move] → Move
Assume that in the list of moves given to a Strategy, the most recent move appears first.
a) Write a Strategy that ignores the opponent's moves and plays Rock, then Paper, then Scissors, then Rock…
b) Write a Strategy that plays whatever will beat the opponent's last move.
c) Write a Strategy that chooses the move that the opponent has played most often in the past, and plays whatever will beat that.
d) Write a function play :: Int → Strategy
→ Strategy → IO () that simulates a given number of games
between two strategies. It should produce output that looks like
this:
game 1: p1 = Paper, p2 = Scissors (p2 wins) game 2: p1 = Rock, p2 = Rock (draw) game 3: p1 = Rock, p2 = Paper (p2 wins) total: p1 won 0, p2 won 2, 1 draw
Consider this type defining a state space:
type StateSpace s a = (s -> [a], s -> a -> s)
In the type declaration above, s is a state type and a is an action type. The first function returns a list of possible actions in any state. The second function takes a state S and an action A, and returns a state that results from performing the action A in S.
Write a function
solve :: Eq s => StateSpace s a -> s -> (s -> Bool) -> Maybe [a]
that takes a state space, a start state and a function that
determines whether a given state is a goal.
The function should find the shortest path from the start state to
any goal state, and should return a list of actions along that path.
If no goal state can be reached, return Nothing.
Three missionaries and three cannibals wish to cross a river using a boat that can carry only two people. At no time may the cannibals outnumber the missionaries on either river bank, since then they would eat the missionaries. How can they cross? Write a Haskell program that can find the shortest solution.
A farmer is on the south bank of a river with a wolf, a goat, and a cabbage. He has a boat that can hold him plus any one of these three items. If the wolf and goat are left alone without the farmer, the wolf will eat the goat. If the goat and cabbage are left alone without the farmer, the goat will eat the cabbage. The wolf does not like cabbage.
How can the farmer cross with all of these possessions to the north bank? Write a Haskell program that can determine the shortest solution.
Three jugs have capacity 8, 5 and 3 liters. Initially the first jug is full of water, and the others are empty.
We can pour water between the jugs, but they have no markings of any sort, so we can pour between two jars only until one of them becomes full or empty.
What sequence of moves can we make so that the jugs will hold 4, 4, and 0 liters of water, respectively?
Write a Haskell program to find the shortest possible solution.
Four people wish to cross a river using a narrow bridge, which can hold only two people at a time. They have one torch and, because it's night, the bridge crossers must take the torch.
Person A can cross the bridge in 1 minute, B in 2 minutes, C in 5 minutes, and D in 8 minutes. When two people cross the bridge together, they must move at the slower person's pace. Can they all get across the bridge if the torch lasts only 15 minutes? Write a Haskell program that can determine the answer.