ML Self Test - Tutorial Three, Recursion with integers

[ First Question ] Number of questions : 4

Welcome to the multiple choice question session.

This material is based on Tutorial Two of the ML Manual.Nobody is watching or keeping score so feel free to guess or to explore those answers which you suspect or know are wrong.

Some of the questions will not be immediately obvious from the tutorial material alone.

ML Self Test - Tutorial Three, Recursion with integers [ Previous Question | Next Question ] 1. Given the following recursive function definition: fun f(a, 0) = 1 | f(a, n) = a * f(a, n-1); Select the value of f(3,4)

a) 0 : int

b) 81 : int

c) 64 : int

d) 27 : int

e) 12 : int

ML Self Test - Tutorial Three, Recursion with integers [ Previous Question | Next Question ] 2. Select the recursive function which defines the sequence 5, 8, 11, 14, 17, 20 ..

fun s(0) = 5
|   s(n) = n + 3;

fun s(0) = 5
|   s(n) = 3*n + 5

fun s(n) = 3 * n + 5;

fun s(0) = 5
|   s(n) = 3 + s(n-1)

e) I don't understand the question.

ML Self Test - Tutorial Three, Recursion with integers [ Previous Question | Next Question ] 3. Select the recursive function which defines the sequence "and his dog", "1 man and his dog""2 man 1 man and his dog", "3 man 2 man 1 man and his dog",...

a) How do concatenate a number onto a string?

fun medow(0) = "and his dog went to mow a medow."
|   medow(n) = makestring n ^
(if n>1 then " men " else " man ") ^ medow(n-1);

fun medow(0) = "and his dog"
|   medow(n) = n ^ " man " ^ medow(n-1);

fun medow(0) = "and his dog"
|   medow(n) = makestring n ^ " man " ^ medow(n-1);

fun medow(0) = " and his dog"
|   medow(n) = makestring n ^ " man" ^ medow(n-1);

ML Self Test - Tutorial Three, Recursion with integers [ Previous Question | Next Question ] 4. Give the type of the following function: fun g x a b = 2*a + 3*b;

a) 'a -> int -> int -> int

b) int -> int -> int

c) ('a * int * int) -> int

d) int -> int -> int -> int

e) (('a -> int) -> int)-> int

ML Self Test - Tutorial Three, Recursion with integers

[ Return to Question ]

1.Given the following recursive function definition:

fun f(a, 0) = 1
|   f(a, n) = a * f(a, n-1);

Select the value of f(3,4)

a) 0 : int

Nope.

Note that the base result is 1 - the recursive calls multiply by a. There is no way that 0 can result unless a is 0 (which it isn't).

ML Self Test - Tutorial Three, Recursion with integers

[ Return to Question | Next Question ]

1.Given the following recursive function definition:

fun f(a, 0) = 1
|   f(a, n) = a * f(a, n-1);

Select the value of f(3,4)

b) 81 : int

That's it exactly.

The expression f(a,n) gives the result aⁿ.We end up with 1 being multiplied by a n times.

ML Self Test - Tutorial Three, Recursion with integers

[ Return to Question ]

1.Given the following recursive function definition:

fun f(a, 0) = 1
|   f(a, n) = a * f(a, n-1);

Select the value of f(3,4)

c) 64 : int

An easy mistake to make.

64 is 4³ - you have it the wrong way around.

ML Self Test - Tutorial Three, Recursion with integers

[ Return to Question ]

1.Given the following recursive function definition:

fun f(a, 0) = 1
|   f(a, n) = a * f(a, n-1);

Select the value of f(3,4)

d) 27 : int

'fraid not.

The call results in four recursions, perhaps you only did three.

ML Self Test - Tutorial Three, Recursion with integers

[ Return to Question ]

1.Given the following recursive function definition:

fun f(a, 0) = 1
|   f(a, n) = a * f(a, n-1);

Select the value of f(3,4)

e) 12 : int

No chance.

You are guessing aren't you? Consider the following sequence.

f(3,1) = 3 * f(3,0)
       = 3 * 1
       = 3

f(3,2) = 3 * f(3,1)
       = 3 * 3
       = 9

f(3,3) = 3 * f(3,2)
       = 3 * 9
       = 25

ML Self Test - Tutorial Three, Recursion with integers

[ Return to Question ]

2.Select the recursive function which defines the sequence 5, 8, 11, 14, 17, 20 ..

fun s(0) = 5
|   s(n) = n + 3;

No that is not right.

The second equation is not recursive - it defines s(n) in terms of n rather than using s(n-1).

ML Self Test - Tutorial Three, Recursion with integers

[ Return to Question ]

2.Select the recursive function which defines the sequence 5, 8, 11, 14, 17, 20 ..

fun s(0) = 5
|   s(n) = 3*n + 5

That's right, but...

The second equation is not recursive - it defines s(n) in terms of n rather than using s(n-1). Although this answers is a better definition in many ways the question asks for a recursive definition. (Note also that the first equation is redundant here.)

ML Self Test - Tutorial Three, Recursion with integers
[ Return to Question ]

2.Select the recursive function which defines the sequence 5, 8, 11, 14, 17, 20 ..

c)
fun s(n) = 3 * n + 5;

That's right, but....
This defines the sequence very neatly - however we want a recursive definition.

ML Self Test - Tutorial Three, Recursion with integers
[ Return to Question | Next Question ]

2.Select the recursive function which defines the sequence 5, 8, 11, 14, 17, 20 ..

d)
fun s(0) = 5 | s(n) = 3 + s(n-1)

That's it.
Each value in the sequence is three more than the previous. The first element of the sequence is five. The two equations given state this.

ML Self Test - Tutorial Three, Recursion with integers
[ Return to Question ]

2.Select the recursive function which defines the sequence 5, 8, 11, 14, 17, 20 ..

e) I don't understand the question.

Sorry - it's not very clear.
A function which takes a single integer as input may be considered to be an infinite sequence of values. s(0) is the first (in this case 5), s(1) is the second (in this case 8). The function required gives the following:
s(0) = 5 s(1) = 8 s(2) = 11 s(3) = 14 ...

ML Self Test - Tutorial Three, Recursion with integers
[ Return to Question ]

3.Select the recursive function which defines the sequence "and his dog", "1 man and his dog""2 man 1 man and his dog", "3 man 2 man 1 man and his dog",...

a) How do concatenate a number onto a string?

Use makestring.
The overloaded function makestring can be used to turn a variety of of things into strings - here we use it on integers.

ML Self Test - Tutorial Three, Recursion with integers
[ Return to Question ]

3.Select the recursive function which defines the sequence "and his dog", "1 man and his dog""2 man 1 man and his dog", "3 man 2 man 1 man and his dog",...

b)
fun medow(0) = "and his dog went to mow a medow." | medow(n) = makestring n ^ (if n>1 then " men " else " man ") ^ medow(n-1);

Get out of here.
That's just showing off.

ML Self Test - Tutorial Three, Recursion with integers
[ Return to Question ]

3.Select the recursive function which defines the sequence "and his dog", "1 man and his dog""2 man 1 man and his dog", "3 man 2 man 1 man and his dog",...

c)
fun medow(0) = "and his dog" | medow(n) = n ^ " man " ^ medow(n-1);

Missed something.
You cannot concatenate an integer to a string.

ML Self Test - Tutorial Three, Recursion with integers
[ Return to Question | Next Question ]

3.Select the recursive function which defines the sequence "and his dog", "1 man and his dog""2 man 1 man and his dog", "3 man 2 man 1 man and his dog",...

d)
fun medow(0) = "and his dog" | medow(n) = makestring n ^ " man " ^ medow(n-1);

That's right.
Well done.

ML Self Test - Tutorial Three, Recursion with integers
[ Return to Question ]

3.Select the recursive function which defines the sequence "and his dog", "1 man and his dog""2 man 1 man and his dog", "3 man 2 man 1 man and his dog",...

e)
fun medow(0) = " and his dog" | medow(n) = makestring n ^ " man" ^ medow(n-1);

Close but not right.
Look closely at the spaces. There is an unnecessary leading space in medow(0), and there is no space between the word man and the next number.

ML Self Test - Tutorial Three, Recursion with integers
[ Return to Question | Next Question ]

4.Give the type of the following function:
fun g x a b = 2*a + 3*b;

a) 'a -> int -> int -> int

That's it.
The first parameter is unused and so may take any value.The second and third must be integers. We should read the type as'a ->(int ->(int -> int)) currying means that g is a function which returns a function which returns another function which returns an integer.

ML Self Test - Tutorial Three, Recursion with integers
[ Return to Question ]

4.Give the type of the following function:
fun g x a b = 2*a + 3*b;

b) int -> int -> int

Nope.
Perhaps you missed the parameter x which appears on the left hand side but not on the right - even though it is unused it still affects the function type.

ML Self Test - Tutorial Three, Recursion with integers
[ Return to Question ]

4.Give the type of the following function:
fun g x a b = 2*a + 3*b;

c) ('a * int * int) -> int

Incorrect.
This is a curried function, your answer fits a function of a tuple. To get this answer the definition would have been
fun g(x,a,b) = 2*a + 3*b;

ML Self Test - Tutorial Three, Recursion with integers
[ Return to Question ]

4.Give the type of the following function:
fun g x a b = 2*a + 3*b;

d) int -> int -> int -> int

Not general enough.
We cannot deduce the type of the first parameter.

ML Self Test - Tutorial Three, Recursion with integers
[ Return to Question ]

4.Give the type of the following function:
fun g x a b = 2*a + 3*b;

e) (('a -> int) -> int)-> int

Yuk.
This type denotes a function which has a function as an input and and int as an output.Your ordinary curried function takes a simple input and gives a function as the output.

ML Self Test - Tutorial Three, Recursion with integers
[ Previous Question | Back home ]
That is all for now.