II 4 : 2001 11 7 keywords: 1 OCaml OCaml (first-class value) (higher-order function) 1.1 1 2 + 2 2 + + n 2 sqsum 1 3 + 2 3 + + n 3 cbsum # let rec sqsum n = # if n = 0 then 0 else n * n + sqsum (n - 1) # let rec cbsum n = # if n = 0 then 0 else n * n * n + cbsum (n - 1);; val sqsum : int -> int = <fun> val cbsum : int -> int = <fun> n 0 0 n n 1
# let rec sigma (f, n) = # if n = 0 then 0 else f n + sigma (f, n-1);; val sigma : (int -> int) * int -> int = <fun> sigma f n ( : * -> * ) sqsum cbsum # let square x = x * x # let sqsum n = sigma (square, n) # let cbsum n = # let cube x = x * x * x in sigma (cube, n);; val square : int -> int = <fun> val sqsum : int -> int = <fun> val cbsum : int -> int = <fun> cbsum let- # sqsum 5;; - : int = 55 # cbsum 5;; - : int = 225 1.2 n sigma f(i) f i=0 let f (anonymous function) OCaml OCaml fun -> e e fun # let cbsum n = sigma ((fun x -> x * x * x), n);; val cbsum : int -> int = <fun> # let sq5 = ((fun x -> x * x), 5) in # sigma sq5;; - : int = 55 # (fun x -> x * x) 7;; - : int = 49 2
( ) fun () (, n x * x * x n fun () ) let let f x = e let f = fun x -> e (fun) 1.3 OCaml 1 Haskell Curry (curried function) x y e x y e s 1, s 2 s 1 s 2 # let concat (s1, s2) = s1 ^ s2 ;; val concat : string * string -> string = <fun> ( ) concat ("abc", "def") # let concat_curry s1 = fun s2 -> s1 ^ s2;; val concat_curry : string -> string -> string = <fun> concat_curry fun s2 ( ) s1 concat_curry string -> (string -> string) 2 # (concat_curry "abc") "def";; - : string = "abcdef" 3
(...) abc (...) "def" (partial application) Mr. ( ) # let add_title = concat_curry "Mr. ";; val add_title : string -> string = <fun> # add_title "Igarashi";; - : string = "Mr. Igarashi" add_title fun s2 -> "Mr. " ^ s2 fun OCaml fun let fun # let concat_curry s1 s2 = s1 ^ s2;; val concat_curry : string -> string -> string = <fun> # let concat_curry = fun s1 s2 -> s1 ^ s2;; val concat_curry : string -> string -> string = <fun> fun 1 -> fun 2 ->... fun n -> e fun 1 2... n -> e (let ) (((f x) y) z) f x y z ( ) t1 -> t2 -> t3 -> t4 t1 -> (t2 -> (t3 -> t4)) 4
/ +, ^ (infix operator) (int->int->int ) OCaml ( ) + ( ) ( ) # (+);; - : int -> int -> int = <fun> # ( * ) 2 3;; - : int = 6 * / mod, *, =, or, & 1 =, <, >, @, ^,, &, +, -, *, /, $, % 2!, $, %, *, +, -,., /, :, <, =, >,?, @, ^, ~ ( ) # let (^-^) x y = x * 2 + y * 3;; val ( ^-^ ) : int -> int -> int = <fun> # 9 ^-^ 6;; - : int = 36 () # let (!! ) x = x + 1;; val (!! ) : int -> int = <fun> #!!;; Characters 2-4: Syntax error # (!!);; - : int -> int = <fun> #!! 3;; - : int = 4 -, -. 1!,?, ~ 2!, $, %, *, +, -,., /, :, <, =, >,?, @, ^, ~ 1 5
1: -, -. ** *, /, %, mod +, - :: @ ^ = <, not &, && or,, <-, := if ; let, match, fun, function, try 6
1.4 Case Study: Newton-Raphson Newton-Raphson Newton-Raphson f f(x) = 0 g(x) = x f(x) f (x) (g(a) = a a) ( x n = x n 1 f(x n 1 )/f (x n 1 ) ) dx g (x) = g(x + dx) g(x) dx # let deriv f = # let dx = 0.1e-10 in # fun x -> (f(x +. dx) -. f(x)) /. dx;; val deriv : (float -> float) -> float -> float = <fun> f(x) = x 3 3 # deriv (fun x -> x *. x *. x) 3.0;; - : float = 26.9999134161 f x f(x), f(f(x)),... f n (x) = f n 1 (x) f n (x) f n 1 (x) f n (x) # let fixpoint f init = # (* computes a fixed-point of f, i.e., r such that f(r)=r *) # let threshold = 0.1e-10 in # let rec loop x = # let next = f x in # if abs_float (x -. next) < threshold then x # else loop next # in loop init;; val fixpoint : (float -> float) -> float -> float = <fun> Newton-Raphson # let newton_transform f = fun x -> x -. f(x) /. (deriv f x);; val newton_transform : (float -> float) -> float -> float = <fun> 7
Newton-Raphson f(x) = 0 f guess # let newton_method f guess = fixpoint (newton_transform f) guess;; val newton_method : (float -> float) -> float -> float = <fun> # let square_root x = newton_method (fun y -> y *. y -. x) 1.0;; val square_root : float -> float = <fun> # square_root 5.0;; - : float = 2.2360679775 1.5 b Exercise 4.1 f f(x)dx integral f a b π sin xdx 0 a b a n δ i (f (a + (i 1) δ) + f (a + iδ)) δ 2 Exercise 4.2 3.8 pow (pow n x) 3 cube (pow x n) cube pow? Exercise 4.3 fun? Exercise 4.4 3 int -> int -> int -> int (int -> int) -> int -> int (int -> int -> int) -> int 8
2 int * int # let fstint ((x, y) : int * int) = x;; val fstint : int * int -> int = <fun> (int * float) * string # let fst_ifs ((x, y) : (int * float) * string) = x;; val fst_ifs : (int * float) * string -> int * float = <fun>??? (int int * float string) # let fst ((x, y) : a * b) = x;; val fst : a * b -> a = <fun> a b (type variable) (polymorphic function) fst a * b -> a T1, T2 T1 * T2 -> T1 ( a. b.( a * b -> a) ) OCaml # let fst (x, y) = x;; val fst : a * b -> a = <fun> ( (principal type) ) fst a * b -> a ( ) 9
# fst (2, 3);; - : int = 2 # fst ((4, 5.2), "foo");; - : int * float = 4, 5.2 a, b int a int * float b string fst int * int -> int (int * float) * string -> int * float (polymorphism) (parametric polymorphism) ( ) id (identity function) apply # let id x = x;; val id : a -> a = <fun> # let apply f x = f x;; val apply : ( a -> b) -> a -> b = <fun> apply ( a -> b) f a x a f x f x # apply abs (-5);; - : int = 5 # apply abs "baz";; Characters 6-9: This expression has type int -> int but is here used with type string -> a? fst (x, y) x, y apply f x ( ) a * b -> a + (adhoc polymorphism) 10
(subtyping polymorphism) 2.1 let OCaml let( ) x (id ) # (fun x -> (x 1, x 2.0)) id;; Characters 19-22: This expression has type float but is here used with type int x 1 x int float let f x double # let double f x = f (f x);; val double : ( a -> a) -> a -> a = <fun> # double (fun x -> x + 1) 3;; - : int = 5 # double (fun s -> "<" ^ s ^ ">") "abc";; - : string = "<<abc>>" 4 # double double (fun x -> x + 1) 3;; - : int = 7 # double double (fun s -> "<" ^ s ^ ">") "abc";; - : string = "<<<<abc>>>>" let # let fourtimes = double double;; val fourtimes : ( _a -> _a) -> _a -> _a = <fun> _a 11
# fourtimes (fun x -> x + 1) 3;; - : int = 7 # fourtimes;; - : (int -> int) -> int -> int = <fun> # fourtimes (fun s -> "<" ^ s ^ ">") "abc";; Characters 35-40: This expression has type string but is here used with type int fourtimes int (value polymorphism) ( ) fourtimes # let fourtimes f = double double f # (* equivalent to "let fourtimes = fun f -> double double f" *) ;; val fourtimes : ( a -> a) -> a -> a = <fun> ( fun ) # fourtimes (fun x -> x + 1) 3;; - : int = 7 # fourtimes (fun s -> "<" ^ s ^ ">") "abc";; - : string = "<<<<abc>>>>" 2.2 OCaml fun x -> x + 1 int -> int + int -> int -> int int x + x int 1 int OK x int x + 1 int x + 1 int x int -> int OCaml 1 12
if ( x a int ) fun x -> if x then 1 else x if if bool then else x a int = a = bool let ( ) apply f, x a, b f x f x c a = b -> c fun f x -> f x a -> b -> c ( b -> c) -> b -> c / / Newton-Raphson let square_root x = newton_method (fun y -> y *. y -. x) 1.0;; newton_method newton_method y float fun (y : float) ->... fst # let fst ((x, y) : a * a) = x;; val fst : a * a -> a = <fun> # fst (true, 3.2);; Characters 6-15: This expression has type bool * float but is here used with type bool * bool 2.3 Case Study: CPU 13
λ- λ- (OCaml fun ) λ- o OCaml # let o f g x = f (g x);; val o : ( a -> b) -> ( c -> a) -> c -> b = <fun> fun x -> -. (sqrt x) # o ( -. ) sqrt;; - : float -> float -> float = <fun> id ( I ) id f f I # o id (sqrt) 3.0;; - : float = 1.73205080757 K # let k x y = x;; val k : a -> b -> a = <fun> k x x # let const17 = k 17 in const17 4.0;; - : int = 17 S # let s x y z = x z (y z);; val s : ( a -> b -> c) -> ( a -> b) -> a -> c = <fun> OCaml fun (id, double λ- ) S K I S K K # s k k 5;; - : int = 5 λ- 14
2.4 Exercise 4.5 curry curry (2 ) uncurry # let curry f x y = f (x, y);; val curry : ( a * b -> c) -> a -> b -> c = <fun> Exercise 4.6 repeat double, fourtimes f n x # let rec repeat f n x = # if n > 0 then repeat f (n - 1) (f x) else x;; val repeat : ( a -> a) -> int -> a -> a = <fun> fib... let fib n = let (fibn, _) =... in fibn;; Exercise 4.7 funny # (* f <@> g denotes the composition of f and g *) # let ( <@> ) f g x = (f (g x)) ;; val ( <@> ) : ( a -> b) -> ( c -> a) -> c -> b = <fun> # let rec funny f n = # if n = 0 then id # else if n mod 2 = 0 then funny (f <@> f) (n / 2) # else funny (f <@> f) (n / 2) <@> f;; val funny : ( a -> a) -> int -> a -> a = <fun> Exercise 4.8 S K K S K K 1 Exercise 4.9 double double f x f (f (f (f x))) 15