1. Chapter
No exercises available.
2. Chapter
No exercises available.
3. Chapter
3.1. What are the types of the following values?
[’a’,’b’,’c’] (’a’,’b’,’c’) [(False,’0’),(True,’1’)] ([False,True],[’0’,’1’]) [tail,init,reverse]
3.2. What are the types of the following functions?
second xs = head (tail xs) swap (x,y) = (y,x) pair x y = (x,y) double x = x*2 palindrome xs = reverse xs == xs twice f x = f (f x)
4. Chapter
4.1. A safe tail function.
Consider a function safetail that behaves in the same way as tail, except that safetail maps the empty list to the empty list, whereas tail gives an error in this case. Define safetail using:
a conditional expression;
guarded equations;
pattern matching.
Hint: the library function null :: [a] -> Bool can be used to test if a list is empty.
4.2. Give three possible definitions for the logical or operator (||) using pattern matching.
4.3. Redefine the following version of (&&) using conditionals rather than patterns:
True && True = True _ && _ = False
4.4. Do the same for the following version:
True && b = b False && _ = False
5. Chapter
5.1. Without looking at the standard prelude, define the following library functions using recursion:
Decide if all logical values in a list are true: and :: [Bool] -> Bool
Concatenate a list of lists: concat :: [[a]] -> [a]
Produce a list with n identical elements: replicate :: Int -> a -> [a]
Select the nth element of a list: (!!) :: [a] -> Int -> a
Decide if a value is an element of a list: elem :: Eq a => a -> [a] -> Bool
5.2. Define a recursive function
merge :: [Int] -> [Int] -> [Int] that merges two sorted lists of integers to give a single sorted list.
5.3. Define a recursive function
msort :: [Int] -> [Int] that implements merge sort, which can be specified by the following two rules:
Lists of length <= 1 are already sorted;
Other lists can be sorted by sorting the two halves and merging the resulting lists.
5.4. Define a recursive function
sumsq n which computes the sum of the squares of the numbers from 1 to n.
5.5. Prime numbers
A prime number p has only two factors, 1 and p itself. A composite number has more than two factors. Define a function numFactors n which computes the number of factors of n in the range 1..n. Hint: Generalise the problem.
5.6. Towers of Hanoi
The Towers of Hanoi is an ancient puzzle, consisting of a collection of rings of different sizes, and three posts mounted on a base. At the beginning all the rings are on the left-most post as shown, and the goal is to move them all to the rightmost post, by moving one ring at a time from one post to another. But, at no time may a larger ring be placed on top of a smaller one!
Can you find a strategy for solving the puzzle based on recursion? That is, if you already know how to move n-1 rings from one post to another, can you find a way to move n rings? Define a Haskell function hanoi n which computes the number of moves needed to move n rings from one post to another using your strategy? How many moves would be needed to solve the puzzle with ten rings? Legend has it that the original version of the puzzle has 32 rings, and is being solved at this very moment by Bhuddist monks in a monastery. When the puzzle is complete, the world will end.
5.7. Fibonacci
Define a function fib n which returns the nth Fibonacci number. Use it to compute the 5th, 10th, 15th, and 20th Fibonacci number. What do you notice? How many additions does your definition use to compute the 20th Fibonacci number?
Can you find a different definition of fib which behaves more like the hand method?
5.8. Subsequences
Sometimes we want to test whether one string occurs in another, or in general whether one list occurs as a subsequence of another. For example, "and" occurs in "sandy". In this exercise, define a function subsequence :: Eq a => [a] -> [a] -> Bool which tests this.
6. Chapter
6.1. Definiere die folgenden Funktionen:
map
filter
foldr
6.2. Definiere die folgenden Funktionen mit Hilfe von foldr.
map
filter
reverse
6.3. Definiere die folgenden Funktionen:
(.)
all
any
takeWhile
dropWhile
7. Chapter
7.1. Expression Parser
Why does factorising the expression grammar make the resulting parser more efficient?
Extend the expression parser to allow the use of subtraction and division, based upon the following extensions to the grammar:
expr -> term ('+' expr | '-' expr | eps)
term -> factor ('*' term | '/' term | eps)
8. Chapter
8.1. Hangman
Consider the following version of hangman:
One player secretly types in a word.
The other player tries to deduce the word, by entering a sequence of guesses.
For each guess, the computer indicates which letters in the secret word occur in the guess.
The game ends when the guess is correct
Adopt a top-down approach
The action sgetLine reads a line of text from the keyboard, echoing each character as a dash.
The function guess is the main loop, which requests and processes guesses until the game ends.
The function indicates which characters in one string occur in a second string.
sgetLine :: IO String guess :: String -> IO () diff :: String -> String -> String
8.2. Nim
Implement the game of nim in Haskell, where the rules of the game are as follows:
The board comprises five rows of stars:
1: * * * * * 2: * * * * 3: * * * 4: * * 5: *
Two players take it turn about to remove one or more stars from the end of a single row. The winner is the player who removes the last star or stars from the board.
9. Chapter
Using recursion and the function add, define a function that multiplies two natural numbers.
Define a suitable function fold for expressions, and give a few examples of its use.
A binary tree is complete if the two sub-trees of every node are of equal size. Define a function that decides if a binary tree is complete.
9.1. Arithmetic Expressions
Consider the following algebraic data type representing arithmetic expressions:
data Expr = Num Int | Var String | Add Expr Expr | Mul Expr Expr
Define a function
differentiate ::: Expr -> String -> Expr
that performs symbolic differantiation.
Define a function
formatExpr :: Expr -> String
that unparses expressions into strings.
Define a function
symplify :: Expr -> Expr
that performs basic simplficications of expressions such as a*1=a, a+0=a.
10. Chapter
10.1. A type class for addresses
Write a type class Address that supports the following operations:
name :: Address a => a -> String street :: Address a => a -> String zipCode :: Address a => a -> Int city :: Address a => a -> String
Write at least two different instances of this type class.
10.2. A type class for points
There are (at least) two different ways how a point in the plane can be represented:
cartesian coordinates
polar coordinates
Implement these two representations with two data types.
Write a type class Point that abstracts over the representation; that is, Point should provide the following operations:
getX :: Point p => p -> Real getY :: Point p => p -> Real getRadius :: Point p => p -> Real getAngle :: Point p => p -> Real
Make the two datatypes representing points an instance of this type class.
11. Chapter
11.1. Write the instance declaration (Monad Maybe)
Write the instance declaration for Monad Maybe. You may need to define a fresh datatype Maybe' because there is a conflicting instance declaration in the Prelude.
11.2. Write the instance declaration (Monad (Either String))
Write the instance declaration for Monad (Either String). You must start GHCi with the option -fglasgow-exts as this instance requires an extension to Haskell 98.
11.3. Implement set, get, runST for state monads
Implement the operations set, get, runST for the state transformer monad ST as discussed in the lecture.
11.4. Add an operation counter to the eval function
Add an counter to the eval function that is incremented every time an addition or division is performed. Hint: You need a state monad.
11.5. Extended the state monad (difficult!)
Extend the well-known state monad (see Control.Monad.State in the hierarchical libraries), and add some extra features to it.
The first step is to introduce a type constructor for the new monad:
data StateMonadPlus s a = ...
The type variables s and a have the standard meaning: s is the type of the state to carry and a is the type of the return value. Make the new monad an instance of the MonadState type class. Hence, you have to include:
import Control.Monad.State
The MonadState type class uses a functional dependency: this is an extension of Haskell 98 type classes. For now, it is sufficient to know that some compiler flags have to be set to enable the extensions that are necessary. The easiest way is to include the following pragma on the first line of your program.
{-# OPTIONS -fglasgow-exts #-}
11.5.1. Feature 1: Diagnostics
We want to gather information about the number of calls to all primitive functions that work on a StateMonadPlus. For this, you have to write a function diagnostics with the following type.
diagnostics :: StateMonadPlus s String
This function should count the number of binds (>>=) and returns (and other primitive functions) that have been encountered, including the call to diagnostics at hand. Secondly, provide a function
annotate :: String -> StateMonadPlus s a -> StateMonadPlus s a
which allows a user to annotate a computation with a given label. The functions for Feature 2 and Feature 3, as well as get and put, should also be part of the diagnosis.
Example:
do return 3 >> return 4 return 5 diagnostics
gives "[bind=3, diagnostics=1, return=3]" as return value. Note that >> is implemented using >>=, and thus also counts as a bind.
11.5.2. Feature 2: Failure
A second feature of your monad is that it can fail during a computation. The Monad type class offers the following member function:
fail :: forall m a. (Monad m) => String -> m a
Calling this function should not result in an exception. To facilitate this, the function runStateMonadPlus (which will be explained later) returns an Either value: Left indicates that the computation failed, Right indicates success. You may have to change the StateMonadPlus data type to cope with this.
11.5.3. Feature 3: History of states
The last feature is to save the current state, and to restore a previous state as the current state. Include the following type class definition in your code, and make StateMonadPlus an instance of this type class.
class MonadState s m => StoreState s m | m -> s where saveState :: m () loadState :: m ()
Saving and loading states should be implemented as a stack: saving a state means pushing the current state on the stack, while loading a state means popping a state from the stack to replace the current one. If loadState is called with an empty stack, then the computation in the monad should fail (as explained for Feature 2).
Example:
do i1 <- get ; saveState modify (*2) i2 <- get ; saveState modify (*2) i3 <- get ; loadState i4 <- get ; loadState i5 <- get return (i1, i2, i3, i4, i5)
returns the value (1,2,4,2,1) if we start with the state consisting of the integer 1.
11.5.4. Running the monad
You have to write a function
runStateMonadPlus :: StateMonadPlus s a -> s -> Either String (a, s)
for running the monad. Given a computation in the StateMonadPlus and an initial state, runStateMonadPlus returns either an error message if the computation failed, or the result of the computation and the final state.
To complete this exercise, you also have to think about which functions should be exposed to outside this module, and which functions should be hidden (and only be visible inside the current module). You might want to consider re-exporting all functionality offered by the Control.Monad.State module.
11.5.5. Further questions
Check the monad laws for your implementation of StateMonadPlus.
What are the modifications required to make a monad transformer for StateMonadPlus?
Suppose that we want to write a function
diagnosticsFuture :: StateMonadPlus s String
which provides information about the computations in StateMonadPlus that are still to come. Explain how this would affect your code. If you feel that such a facility cannot be implemented, then you should give some arguments for your opinion. If you believe it can be done, implement it.