User Tools

Site Tools


ex-hof-sol

Differences

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

Link to this comparison view

ex-hof-sol [2015/10/08 15:20] (current)
Line 1: Line 1:
 +====== LiP assignment #3: solutions ======
 +
 +===== 1. Fix point =====
 +
 +<code ocaml>
 +# 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>
 +</​code>​
 +
 +\\
 +
 +===== 2. Min-Max =====
 +
 +<code ocaml>
 +# 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)
 +</​code>​
 +
 +\\
 +
 +
 +===== 3. Monotonicity test =====
 +
 +<code ocaml>
 +# 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"​
 +</​code>​
 +
 +\\
 +
 +
 +===== 4. Fibonacci ===== 
 +
 +<code ocaml>
 +# 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>
 +</​code>​
 +
 +\\
 +
 +
 +===== 5. Bounded iteration with index ===== 
 +
 +<code ocaml>
 +# 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
 +</​code>​
 +
 +<code ocaml>
 +# 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>
 +</​code>​
 +
 +\\
 +
 +
 +===== 6. Quiz game ===== 
 +
 +<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
 +;;
 +
 +# 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>
 +</​code>​
 +
 +\\
 +
  
ex-hof-sol.txt ยท Last modified: 2015/10/08 15:20 (external edit)