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 `a``b`, 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.

```#load "str.cma"

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 