User Tools

Site Tools


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 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
;;
 
# 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>


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