ex-hof

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

— |
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)