Write a function isPerm
::
[Int]
-> Bool
that takes a list of N integers and returns True
if the list holds some permutation of the integers 1, .., N. Your
function should run in O(N). Hint: Use the accumArray
function.
Write a function minCoins
::
[Int]
->
Int
->
Maybe
[Int]
that takes a list of coin denominations and a sum, and returns
a minimal list of coins which can be used to form the sum. Any
denomination may be used multiple times in forming the sum. For
example, min_coins
[1,
2,
5,
10]
9
might return Just
[2,
2,
5].
If the sum cannot be formed from the given coins, return Nothing.
Write a function partition
::
[Int]
->
Maybe
([Int],
[Int])
that takes a list of integers and determines whether it can be
partitioned into two sets whose sum is equal. If so, the function
should return a Just with two lists containing the
numbers in each set. If not, it should return Nothing.
Consider the following game for two players. A counter starts at some integer N. On each player's turn, they may reduce the counter by any integer that is a perfect square, without ever going below 0. The first player who reaches 0 wins.
a) Write a function wins
::
Int
->
Bool
that takes a starting integer N and returns True
if the first player can always win the game.
b) Write a function wins2 that is
like wins, but if the first player can always win, it
returns Just k, where k is some perfect square that the
first player should subtract in their first move. If the first player
cannot always win, the function should return Nothing.
c) Write a function win3 that is like
wins2, but uses dynamic programming for an efficient
implementation.
Write a function csort
::
(Int,
Int)
->
[Int]
->
[Int]
that implements a counting sort. (csort (lo, hi)
xs) should sort a list xs of values, all of which
are in the range lo ≤ x ≤ hi. It should run in O(N), where N =
length xs.
Implement a radix sort. Given any base d, your function should be able to sort N numbers in the range 1 .. R in time O(N · logd(R)), using much less memory than a counting sort.
The replacement operator <$ works with any functor, and injects a given value. For example:
> 3 <$ Just 5 Just 3 > 3 <$ Nothing Nothing > 3 <$ [10, 20, 30] [3,3,3]
a) What is the type of <$?
b) Implement <$.
In Haskell, we may write the type (t ->
u) as ((->) t u). For example, (Int ->
Int) is the same as ((->) Int Int).
a) What is the kind of (->)?
b) What is the kind of ((->) Int)?
c) Based on its kind, could ((->) Int)
belong to the Functor type class? Perform experiments to
determine whether it is indeed a member of this type class and, if
so, how fmap behaves on a function of this type.
d) Declare that ((->) a) is an
instance of Functor.
Rewrite the expression [(x, y) | x <-
[1..3], y <- [1..4]] using no variables, by using the
applicative functor operator <*>.
Import the Haskell Prelude without the Either
type or its data constructors:
import Prelude hiding (Either, Left, Right)
a) Define the Either type.
b) Declare that (Either a) is an
instance of Functor.
c) Declare that (Either a) is an
instance of Applicative.
d) Declare that (Either a) is an
instance of Monad. Check that your declaration works by
using Either in a do block.
We may define our own list type as follows:
data List a = Nil | Cons a (List a)
a) Declare that List is an instance of Functor.
b) Declare that List is an instance
of Applicative.
c) Declare that List is an instance
of Monad. Check that your declaration works by using
List in a do block.
Write a function
m_fmap :: Monad m => (a -> b) -> m a -> m b
that works like fmap, but is implemented using the >>=
operator.
Write a function
m_apply :: Monad m => m (a -> b) -> m a -> m b
that works like <*>, but is implemented using the >>= operator.
The *> operator works with any Applicative
type. It combines two values, discarding the value of the first. For
example:
> Just 3 *> Just 4 Just 4 > Just 3 *> Nothing Nothing > Nothing *> Just 4 Nothing
If the applicative is a monad, a *> b is the same as
do
a
b<* is similar, but discards the value of the second action:
> Just 3 <* Just 4 Just 3
a) What is the type of <* and *>?
b) Suppose that an applicative is a monad. Write a
do block that is equivalent to a <* b.
c) Implement <* and *>.
The function sequence has type
sequence :: Monad m => [m a] → m [a]
It combines a list of monadic values into a single monadic value. For example:
> sequence [Just 4, Just 3, Just 2] Just [4,3,2] > sequence [Just 4, Nothing, Just 2] Nothing
sequence [a, b, c] is the same as
do x <- a y <- b z <- c return [x, y, z]
Implement sequence.
In Haskell, we may represent a graph in adjacency-list representation using an association list that maps each vertex to a list of its neighbors:
type Graph a = [(a, [a])]
For example, consider this undirected graph:
We may represent it as
graph = [ ('a', "ce"), ('b', "de"), ('c', "adf"), ('d', "bcef"),
('e', "bdf"), ('f', "cdeg"), ('g', "f") ]a) Write a function
adjacent :: Eq a => Graph a -> a -> [a]
that returns a list of a vertex's neighbors in a graph.
b) Write a function
paths :: Eq a => Graph a -> a -> a -> [[a]]
that takes a graph and the ids of start and end vertices v and w, and returns a list of all possible paths from v to w, where a path is represented as a list of vertices. A path may not contain the same vertex twice.
Write a function
dfs :: Eq a => Graph a -> a -> [a]
that takes a graph and the id of a start vertex v, and returns a list of all vertices that are reachable from v. Use a depth-first search, and return the list of vertices in the order in which they were discovered.
Write a function that takes a graph and the ids of
start and end vertices v and w, and returns a list of vertices on the
shortest path from v to w, or Nothing if there is no
such path. Use a breadth-first search.
Write a function that takes a graph in adjacency
list representation and returns a 3-coloring of the graph if one
exists, or otherwise Nothing.
A mini-Sudoku puzzle looks like this:
To solve the puzzle, you must place a number from 1 to 4 in every square so that the numbers in every row, column, and mini-square are distinct.
Write a program that reads a mini-Sudoku puzzle from standard input. Empty squares will be represented by the number 0:
3040 0103 2300 1002
The program should print out a solution to the puzzle if it can find one; otherwise it should print "no solution".
Write a program that reads a rectangular maze from standard input in the following format:
#####.### #...#...# #.#...#.# #.#####.# #.....#.# ###.#####
If there is any possible path from the top to the bottom, the program should print out the maze, highlighting some such path:
#####x### #xxx#x..# #x#xxx#.# #x#####.# #xxx..#.# ###x#####
If there is no such path, it should print "no path".
a) Write a function that takes a directed graph
and returns True if the graph is cyclic, otherwise
False.
b) Modify your function to work on an undirected graph.
In an undirected graph, a Hamiltonian cycle is a cycle that visits every vertex exactly once. A graph possessing a Hamiltonian cycle is said to be Hamiltonian.
Write a function that takes a graph in adjacency-list representation and returns a list containing the vertices in any Hamiltonian cycle in the graph, or Nothing if there is none.
Write a function that takes two graphs in adjacency list representation and returns true if the graphs are isomorphic.
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 function
that return a list of actions that will solve the puzzle, or Nothing
if it is not possible.