User Tools

Site Tools


ex-hof

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

ex-hof [2015/10/08 15:20] (current)
Line 1: Line 1:
 +====== LiP assignment #3 ======
 +
 +
 +===== 1. Fixpoint =====
 +
 +Write a function ''​fix''​ with the following type:
 +<code ocaml>
 +fix: (int -> int) -> int
 +</​code>​
 +
 +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:
 +<code ocaml>
 +minmax : (int -> 'a) -> int -> int -> 'a * 'a
 +</​code>​
 +
 +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 (F<​sub>​i</​sub>​)<​sub>​i</​sub>,​
 +defined as follows:
 + 
 +F<​sub>​0</​sub>​=0 ​
 +
 +F<​sub>​1</​sub>​=1
 +
 +F<​sub>​i</​sub>​=F<​sub>​i-1</​sub>​+F<​sub>​i-2</​sub>​ if i>​1. ​
 +
 +//Hint:// use the  ''​iter''​ combinator given [[hof#​bounded_iterators|here]],​ and exploit the fact that
 +(F<​sub>​n+2</​sub>,​ F<​sub>​n+1</​sub>​) can be written as ''​f''​ (F<​sub>​n+1</​sub>,​ F<​sub>​n</​sub>​),​
 +for some function ''​f:​ int * int -> int * int''​. ​
 +
 +\\
 +
 +
 +===== 5. Bounded iteration with index =====
 +
 +First of all, use the ''​iter''​ combinator given [[hof#​bounded_iterators|here]] to provide an alternative characterization of the following functions:
 +  *  factorial function ​
 +  * ''​summation''​ function, ​ defined recursively as follows:
 +<code ocaml>
 +let rec summation f a b =
 +  if a>b then 0
 +  else (f a) + summation f (a+1) b;;
 +</​code>  ​
 +
 +
 +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.
 +<code ocaml>
 +#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
 +;;
 +</​code>​
  
ex-hof.txt · Last modified: 2015/10/08 15:20 (external edit)