ex-hof

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.

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]`

.

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.

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

F_{0}=0

F_{1}=1

F_{i}=F_{i-1}+F_{i-2} if i>1.

*Hint:* use the `iter`

combinator given here, and exploit the fact that
(F_{n+2}, F_{n+1}) can be written as `f`

(F_{n+1}, F_{n}),
for some function `f: int * int → int * int`

.

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.

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 let rec ask last_answer_was_bad = let () = Printf.printf "%s%s" (if last_answer_was_bad then "Please enter an integer.\n" else "") query in match (int_from_string (read_line ())) with | None -> ask true | Some n -> n in ask false ;;

ex-hof.txt · Last modified: 2015/10/08 15:20 (external edit)