ex-hof

LiP assignment #3

1. Fixpoint

Write a function fix with the following type:

fix: (int -> int) -> int

When fed with a function f: int → int, the expression fix f evaluates to the minimum non-negative integer fixed point of f, i.e. the minimum x≥0 such that f(x) = x. If no such fixed point exists, fix f diverges.

For instance, fix (fun x → x*x - 20) evaluates to 5.

2. Min-Max

Write a function minmax with the following type:

minmax : (int -> 'a) -> int -> int -> 'a * 'a

When fed with a function f: int → int and two integers a,b such that ab, the expression minmax f a b evaluates to a pair (min,max), where min and max are, respectively, the minimum and the maximum of f in the range [a,b].

3. Monotonicity test

Write a function test that, when fed with a function f: int → int and two integers a,b, evaluates to the string:

• “constant”, if f is constant in the range [a,b]
• “strictly increasing”, if f is strictly increasing in the range [a,b]
• “strictly decreasing”, if f is strictly decreasing in the range [a,b]
• “increasing”, if f is increasing in the range [a,b]
• “decreasing”, if f is decreasing in the range [a,b]
• “non monotone” if none of the items above applies

Hint. Start writing a function increasing that, taken as input a function f: int → int and two integers a,b, evaluates to true if f is increasing in the range [a,b], otherwise evaluates to false. Then, generalise it to a function monotone : (int → 'a) → ('a → 'a → bool) → int → int → bool, which takes as parameter also an order relation with type ('a → 'a → bool). Recall that you can pass arithmetical operators ( such as: (<), (>), etc. ) as parameters.

4. Fibonacci

Write a linear-time algorithm to compute the n-th element of the Fibonacci sequence (Fi)i, defined as follows:

F0=0

F1=1

Fi=Fi-1+Fi-2 if i>1.

Hint: use the iter combinator given here, and exploit the fact that (Fn+2, Fn+1) can be written as f (Fn+1, Fn), for some function f: int * int → int * int.

5. Bounded iteration with index

First of all, use the iter combinator given here to provide an alternative characterization of the following functions:

• factorial function
• summation function, defined recursively as follows:
let rec summation f a b =
if a>b then 0
else (f a) + summation f (a+1) b;;

Then, define a function iter2 with type int → (int → 'a → 'a) → 'a → 'a such that:

• iter2 0 f x = f 0 x
• iter2 1 f x = f 1 (f 0 x)
• iter2 2 f x = f 2 (f 1 (f 0 x))
• iter2 3 f x = f 3 (f 2 (f 1 (f 0 x)))

Finally, use iter2 to provide alternative definitions for the factorial and for the summation functions.

6. Quiz game

Write a quiz game, that asks the user to guess a random number between 1 and 100. When the user does not guess right, he is informed if the guess is too low or too high, and then he is asked for a new guess.

Hint. Use the function Random.int, which takes an integer argument n and evaluates to a random integer in the range [0,n-1]. The following code snippet is a function that, taken as input a string, prints it out, asks the user to enter an integer, and returns that integer.

let user_query_int query =
let rx_int = Str.regexp "^[ \t]*\\(-?[0-9]+\\)[ \t\n\r]*\$" in
let int_from_string s =
if Str.string_match rx_int s 0
then Some (int_of_string (Str.matched_group 1 s))
else None
in 