Try to work these out on paper, and then check by typing them in. Remember that the type of an expression is the type of the value it will evaluate to. Can you show the steps of evaluation for each expression?
Type each expression in. What number does each evaluate to? Can you
work out which operator (mod or +) is being
calculated first?
Type it in. What does OCaml print? What is the evaluation order?
What if a value of 2 appeared? How might we interpret it?
The function takes one integer, and returns that integer multiplied by ten. So what must its type be?
What does the function take as arguments? What is the type of its
result? So what is the whole type? You can use the <>
and && operators here.
This will be a recursive function, so remember to use
let rec. What is the sum of all the
integers from 1…1? Perhaps this is a
good base case.
This will be a recursive function. What happens when you raise a number to the power 0? What about the power 1? What about a higher power?
Can you define this in terms of the isvowel function we
have already written?
Try adding parentheses to the expression in a way which does not change its meaning. Does this make it easier to understand?
When does it not terminate? Can you add a check to see when it might happen, and return 0 instead? What is the factorial of 0 anyway?
We are pattern matching on a boolean value, so there are just two
cases: true and false.
Convert the if
… then
… else structure of the
sum function from the previous chapter into a pattern
matching structure.
You will need three cases as before – when the power is 0, 1 or greater than 1 – but now in the form of a pattern match.
Consider where parentheses might be added without altering the expression.
There will be two cases in each function – the special range pattern
x..y, and _ for any other character.
Consider three cases: (1) the argument list is empty, (2) the
argument list has one element, (3) the argument list has more than one
element a::b::t. In the last case, which element do we need
to miss out?
The function will have type bool
list→ int. Consider the empty list,
the list with true as its head, and the list with
false as its head. Count one for each true and
zero for each false.
The function to make a palindrome is trivial; to detect if a list is a palindrome, consider the definition of a palindrome – a list which equals its own reverse.
Consider the cases (1) the empty list, (2) the list with one element, and (3) the list with more than one element. For the tail recursive version, use an accumulating argument.
Can any element exist in the empty list? If the list is not empty, it must have a head and a tail. What is the answer if the element we are looking for is equal to the head? What do we do if it is not?
The empty list is already a set. If we have a head and a tail, what does it tell us to find out if the head exists within the tail?
Consider in which order the @ operators are evaluated in
the reverse function. How long does each append take? How many are
there?
Consider adding another let before
let left and
let right.
Consider the situations in which take and
drop can fail, and what arguments msort gives
them at each recursion.
This is a simple change – consider the comparison operator itself.
What will the type of the function be? Lists of length zero and one are already sorted – so these will be the base cases. What do we do when there is more than one element?
You can put one let rec construct
inside another.
The function calm is simple recursion on lists. There
are three cases – the empty list, a list beginning with ’!’
and a list beginning with any other character. In the second part of the
question, write a function calm_char which processes a
single character. You can then use map to define a new
version of calm.
This is the same process as Question 1.
Look back at the section on anonymous functions. How can
clip be expressed as an anonymous function? So, how can we
use it with map?
We want a function of the form let rec
apply f n x = … which applies f to
x a total of n times. What is the base case?
What do we do in that case? What otherwise?
You will need to add the extra function as an argument to both
insert and sort and use it in place of the
<= operator in insert.
There are three possibilities: the argument list is empty,
true is returned when its head is given to the function
f, or false is returned when its head is given
to the function f.
If the input list is empty, the result is trivially true – there cannot possibly be any elements for which the function does not hold. If not, it must hold for the first one, and for all the others by recursion.
You can use map on each α
list in the α list list.
Make sure to consider the case of the empty list, where there is no smallest positive element, and also the non-empty list containing entirely zero or negative numbers.
Just put an exception handler around the function in the previous question.
First, write a function to find the number less than or equal to the square root of its argument. Now, define a suitable exception, and wrap up your function in another which, on a bad argument, raises the exception or otherwise calls your first function.
Use the
try … with
construct to call your function and handle the exception you
defined.
The keys in a dictionary are unique – does remembering that fact help you?
The type will be the same as for the add function, but
we only replace something if we find it there – when do we know we will
not find it?
The function takes a list of keys and a list of values, and returns a dictionary. So it will have type α list → β list → (α × β) list. Try matching on both lists at once – what are the cases?
This function takes a list of pairs and produces a pair of lists. So its type must be (α × β) list → α list × β list.
For the base case (the empty dictionary), we can see that the result
should be ([], []). But what to do in the case we have
(k, v) :: more? We must get names for the two parts of the
result of our function on more, and then cons
k and v on to them – can you think of how to
do that?
You can keep a list of the keys which have already been seen, and use
the member function to make sure you do not add to the
result list a key-value pair whose key has already been included.
The function will take two dictionaries, and return another – so you should be able to write down its type easily.
Try pattern matching on the first list – when it is empty, the answer is trivial – what about when it has a head and a tail?
Try building a list of booleans, each representing the result of
member on a list.
The / operator differs from the * operator
in an important sense. What is it?
The type of map is (α →
β)
→ α list → β
list. The type of mapl is (α →
β)
→ α list list → β
list list. So, what must the type of mapll
be? Now, look at our definition of mapl – how can we extend
it to lists of lists of lists?
Use our revised take function to process a single list.
You may then use map with this (partially applied) function
to build the truncate function.
Build a function firstelt which, given the number and a
list, returns the first element or that number. You can then use this
function (partially applied) together with map to build the
main firstelts function.
The type will have two constructors: one for squares, requiring only a single integer, and one for rectangles, requiring two: one for the width and one for the height.
The function will have type rect → int. Work by pattern matching on the two constructors of your type.
Work by pattern matching on your type. What happens to a square. What to a rectangle?
First, we need to rotate the rectangles as needed – you have already
written something for this. Then, we need to sort them according to
width. Can you use our sort function which takes a custom
comparison function for this?
Look at how we re-wrote length and append
for the sequence type.
Add another constructor, and amend evaluate as
necessary.
Handle the exception, and return None in that case.
The type will be α →
α tree → bool. That is, it
takes an element to search for, and a tree containing elements of the
same type, and returns true if the element is found, and
false if not. What happens if the tree is a leaf? What if
it is a branch?
The function will have type α tree → α tree. What happens to a leaf? What must happen to a branch and its sub-trees?
If the two trees are both Lf, they have the same shape.
What if they are both branches? What if one is a branch and the other a
leaf or vice versa?
We have already written a function for inserting an element into an existing tree.
Try using list dictionaries as an intermediate representation. We already know how to build a tree from a list.
Consider using a list of sub-trees for a branch. How can we represent a branch which has no sub-trees?
You can use the print_string and print_int
functions. Be careful about what happens when you print the last
number.
You can use the read_int function to read an integer
from the user. Be sure to give the user proper instructions, and to deal
with the case where read_int raises an exception (which it
will if the user does not type an integer).
One way would be to ask the user how many dictionary entries they intend to type in first. Then we do not need a special code to signal the end of input.
Try writing a function to build a list of integers from 1 to n. Can you use that to build the
table and print it? The iter and/or map
functions may come in useful. Deal with a channel in your innermost
function – the opening and closing of the file can be dealt with
elsewhere.
The input_line function can be used – how many times can
you call it until End_of_file is raised?
We can read lines from the file using input_line and
write using output_string – make sure the newlines do not
get lost! How do we know when we are done? Write a function to copy a
line from one channel to another – we can deal with opening and closing
the files separately.
Consider the initial values of the references, and then work through how each one is altered by each part of the expression. What is finally returned as the result of the expression?
Try creating a value for each list in OCaml. Now try getting the head of the list, which is a reference, and updating its contents to another integer. What has happened in each case?
Try writing a function forloop which takes a function to
be applied to each number, and the start and end numbers. It should call
the given function on each number. What should happen when the start
number is larger than the end number?
Type them in if you are stuck. Can you work out why each expression has the type OCaml prints?
We want a function of type int array → int. Try a for loop with a reference to accumulate the sum.
Consider swapping elements from opposite ends of the array – the problem is symmetric.
To build an array of arrays, you will need a use
Array.make to build an array of empty arrays. You can then
set each of the elements of the main array to a suitably sized array,
again created with Array.make. Once the structure is in
place, putting the numbers in should be simple.
What is the difference between the codes for ’a’ and
’A’? What about ’z’ and ’Z’?
Consider the built-in functions ceil and
floor.
This is simple arithmetic. The function will take two points and return another, so it will have type float × float → float × float → float × float.
Consider the built-in function floor. What should happen
in the case of a negative number?
Calculate the column number for the asterisk carefully. How can it be printed in the correct column?
You will need to call the star function with an
appropriate argument at points between the beginning and end of the
range, as determined by the step.
You can assume List.rev which is tail-recursive.
You might use List.map here, together with
List.mem
The String.iter function should help here.
Try String.map supplying a suitable function.
Consider String.concat.
Create a buffer, add all the strings to it in order, and then return its contents.
String.sub is useful here. You can compare strings with
one another for equality, as with any other type.
You will need to alter the Textstat module to calculate
the histogram and allow it to be accessed through the module’s
interface. Then, alter the main program to retrieve and print the extra
information.
You will need functions to read and write the lines. You can read the
required input and output filenames from Sys.argv. What
should we do in case of an error, e.g. a bad filename?
Consider doing something a very large number of times. You should avoid printing information to the screen, because the printing speed might dominate, and the differing computation speeds may be hard to notice.
Start with a function to search for a given string inside another.
You might find some functions from the String module in the
OCaml Standard Library to be useful, or you can write it from first
principles. Once this is done, the rest is simple.