ex-hof-sol

# Differences

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

 — ex-hof-sol [2015/10/08 15:20] (current) Line 1: Line 1: + ====== 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 = + ​ + + \\ + + ===== 2. Min-Max ===== + + + # let min x y = if x<=y then x else y;; + val min : 'a -> 'a -> 'a = + + # let max x y = if x<=y then y else x;; + val max : 'a -> 'a -> 'a = + + # 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 = + + # 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) -> int -> int -> bool = + + # increasing (fun x -> x*x) (-5) 5;; + - : bool = false + + # let rec monotone f r a b = + if b 'a) -> ('a -> 'a -> bool) -> int -> int -> bool = + + # 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 = + + # 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 = + ​ + + \\ + + + ===== 5. Bounded iteration with index ===== + + + # let fact n = fst (iter n (fun (x,i) -> (i*x,i+1)) (1,1));; + val fact : int -> int = + + # 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 = + + # 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 = + + # let fact n = iter2 n (fun x i -> if i=0 then 1 else i * x) 0;; + val fact : int -> int = + + # 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 = + ​ + + \\ + + + ===== 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 guess secret "Too low! Try again: " + | _ -> guess secret "Too high! Try again: ";; + val guess : int -> string -> unit = + + # let quiz = fun () -> let secret=Random.int(100) in guess secret "Guess a number between 1 and 100: ";; + val quiz : unit -> unit = + ​ + + \\ +
ex-hof-sol.txt ยท Last modified: 2015/10/08 15:20 (external edit)