ex-hof-sol

# LiP assignment #3: solutions

## 1. Fix point

```# let fix f =
let rec fix' f x =
if f x = x then x else fix' f (x+1)
in fix' f 0;;

val fix : (int -> int) -> int = <fun>```

## 2. Min-Max

```# let min x y = if x<=y then x else y;;
val min : 'a -> 'a -> 'a = <fun>

# let max x y = if x<=y then y else x;;
val max : 'a -> 'a -> 'a = <fun>

# let rec minmax f a b =
if b=a then (f(a),f(a))
else if b=a+1 then (min (f a) (f b), max (f a) (f b))
else let (x,y) = minmax f (a+1) b in (min x (f a), max y (f a));;

val minmax : (int -> 'a) -> int -> int -> 'a * 'a = <fun>

# minmax (fun x -> (x+1) * (x-1)) (-5) 5;;
- : int * int = (-1, 24)```

## 3. Monotonicity test

```# let rec increasing f a b =
if b<a then true
else if b=a+1 then f a <= f b
else f a <= f (a+1) && (increasing f (a+1) b);;
val increasing : (int -> 'a) -> int -> int -> bool = <fun>

# increasing (fun x -> x*x) (-5) 5;;
- : bool = false

# let rec monotone f r a b =
if b<a then true
else if b=a+1 then r (f a) (f b)
else r (f a) (f (a+1)) && (monotone f r (a+1) b);;
val monotone : (int -> 'a) -> ('a -> 'a -> bool) -> int -> int -> bool = <fun>

# let test f a b =
if monotone f (=) a b then "constant"
else if monotone f (<) a b then "strictly increasing"
else if monotone f (<=) a b then "increasing"
else if monotone f (>) a b then "strictly decreasing"
else if monotone f (>=) a b then "decreasing"
else "unknown";;
val test : (int -> 'a) -> int -> int -> string = <fun>

# test (fun x -> x*x) 1 5;;
- : string = "strictly increasing"```

## 4. Fibonacci

```# let fib n =
let fibpair n =
(iter n (fun (n1,n2) -> (n2,n1+n2)) (0,1))
in fst (fibpair n);;

val fib : int -> int = <fun>```

## 5. Bounded iteration with index

```# let fact n = fst (iter n (fun (x,i) -> (i*x,i+1)) (1,1));;
val fact : int -> int = <fun>

# fact 5;;
- : int = 120

# let summation f a b = fst (iter
(if b-a<0 then 0 else b-a+1)
(fun (x,i) -> (x + f (a+i-1), i+1))
(0,1)
);;

val summation : (int -> int) -> int -> int -> int = <fun>

# summation (fun x -> x) 1 10;;
- : int = 55

# summation (fun x -> x) 5 4;;
- : int = 0

# summation (fun x -> x) (-3) 3;;
- : int = 0```
```# let rec iter2 n f x = if n=0 then f 0 x else f n (iter2 (n-1) f x);;
val iter2 : int -> (int -> 'a -> 'a) -> 'a -> 'a = <fun>

# let fact n = iter2 n (fun x i -> if i=0 then 1 else i * x) 0;;
val fact : int -> int = <fun>

# let summation f a b = iter2
(if b-a<0 then 0 else b-a+1)
(fun i x -> if i=0 then 0 else x + f (a+i-1))
0;;

val summation : (int -> int) -> int -> int -> int = <fun>```

## 6. Quiz game

```#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 () = Printf.printf "%s%s"
query
in match (int_from_string (read_line ())) with
| Some n -> n
;;

# let rec guess secret msg = match (user_query_int msg) with
y when y=secret -> print_string "You won!"
| y when y<secret -> guess secret "Too low! Try again: "
| _ -> guess secret "Too high! Try again: ";;
val guess : int -> string -> unit = <fun>

# let quiz = fun () -> let secret=Random.int(100) in guess secret "Guess a number between 1 and 100: ";;
val quiz : unit -> unit = <fun>```