User Tools

Site Tools


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:



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, 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
  let rec ask last_answer_was_bad =
    let () = Printf.printf "%s%s"
	(if last_answer_was_bad then "Please enter an integer.\n" else "")
    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)