> ocaml
# 3 * 4;;
- : int = 12
# "Hello " ^ "world!";;
- : string = "Hello world!"
# 3.0 /. 7.0;;
- : float = 0.428571428571428548
# if 1 < 2 then
1
else
1.3
;;
This expression has type float but is here
used with type int
> ocaml # let x = 1;; val x : int = 1 # let y = 2;; val y : int = 2 # let z = x + y;; val z : int = 3You can also nest definitions:
# let x = 2 in
let y = 3 in
x + y;;
- : int = 5
> cat >if.ml
open Printf;;
let i = if 1 < 2 then
3 + 7
else
4;;
printf "%i\n" i;;
^D
> ocamlopt -o if if.ml
> ./if
10
> ocamlc -g -o if_byte if.ml
> ./if_byte
10
> ocaml # let incr i = i + 1;; val incr : int -> int = <fun> # incr 2;; - : int = 3 # incr x;; - : int = 2 # incr 2 * 3;; - : int = 9 # incr (2 * 3);; - : int = 7
# let x = 1;; val x : int = 1 # let add y = x + y;; val add : int -> int = <fun> # let x = 2;; val x : int = 2 # add 5;; - : int = 6
> ocaml
# let rec factorial = function
0 -> 1
| 1 -> 1
| n -> n * factorial(n-1);;
val factorial : int -> int = <fun>
# factorial 4;;
- : int = 24
# factorial 8;;
- : int = 40320
# factorial 1.2;;
This expression has type float but is here
used with type int
> ocaml
# let rec fact_iter product counter max_count =
if counter > max_count then
product
else
fact_iter (counter*product) (counter+1) max_count;;
val fact_iter : int -> int -> int -> int = <fun>
# let factorial2 n = fact_iter 1 1 n;;
val factorial2 : int -> int = <fun>
# factorial2 4;;
- : int = 24
# factorial2 8;;
- : int = 40320
Design ocaml functions to perform exponentiation.
> ocaml
#let rec sum_ints a b =
if a > b then
0
else
a + sum_ints (a+1) b;;
# sum_ints 1 100;;
- : int = 5050
#let rec sum_squares a b =
if a > b then
0
else
a*a + sum_squares (a+1) b;;
# sum_squares 1 10;;
- : int = 385
We can factor out the underlying pattern of the summation, using a function term to calculate each term of the series.
> ocaml
# let rec sum term a b =
if a > b then
0
else
term a + sum term (a+1) b;;
# let identity i = i;;
# sum identity 1 100;;
- : int = 5050
# let square i = i*i;;
# sum square 1 10;;
- : int = 385
In our previous example, the function identity had an unusual type signature, using the type variable 'a instead of a concrete type. Such a function is polymorphic, working on any type.
# let identity i = i;; val identity : 'a -> 'a =# identity 1;; - : int = 1 # identity 1.0;; - : float = 1. # (identity square);; - : int -> int = <fun> # (identity square) 4;; - : int = 16
We can introduce anonymous functions with the fun keyword:
> ocaml # (fun x -> x + 1) 5;; - : int = 6
We can assign names to anonymous functions with the let keyword:
> ocaml # let incr2 = (fun x -> x + 1);; val incr2 : int -> int = <fun> # incr2 5;; - : int = 6
We can introduce anonymous functions with the fun keyword:
> ocaml
# let rec sum2 term next a b =
if a > b then
0
else
term a + sum2 term next (next a) b;;
# let sum_ints2 a b = sum2 (fun x -> x) (fun x -> x + 1) a b;;
# sum_ints2 1 100;;
- : int = 5050
# let skip_sum a b = sum2 (fun x -> x) (fun x -> x + 2) a b;;
# skip_sum 1 100;;
> ocaml
# let rec sum3 term next a b =
if a > b then
0.0
else
term a +. sum3 term next (next a) b;;
# let pi_sum a b = 8.0 *.
sum3 (fun x -> 1.0/.(x*.(x+.2.0))) (fun x -> x+.4.0) a b;;
# pi_sum 1.0 100.0;;
- : float = 3.12159465259101054
# pi_sum 1.0 1000.0;;
- : float = 3.13959265558978284
# pi_sum 1.0 100000.0;;
- : float = 3.14157265358979521
Consider the area under the curve y=f(x) over the interval [a,b]. Divide the interval [a,b] into n subintervals [xk-1,xk] of equal width h = (b-a)/n, where xk=a+kh. The composite Simpson's Rule for n subintervals is:
∫f(x)dx = h/3 ( f(0) + 4 Σ f(x2k+1) + 2 Σ f(x2k) )Create a function simpson that takes arguments f, a, b, and n and returns the value of the integral computed using Simpson's Rule.
> ocaml # let p = 1, 2;; val p : int * int = (1, 2) # let divide x y = x / y, x mod y;; val divide : int -> int -> int * int = <fun> # divide 22 7;; - : int * int = (3, 1) # let first (x,_) = x;; # let second (_,y) = y;; # first p;; - : int = 1 # second p;; - : int = 2 # let q = 1, 2, 3;; val q : int * int * int = (1, 2, 3) # first q;; This expression has type int * int * int but is here used with type 'a * 'b
A list is a sequence of values of the same type.
> ocaml # let x = [1;2;3];; val x : int list = [1; 2; 3] # [];; - : 'a list = [] # [1;2.0];; This expression has type float but is here used with type int
The :: operator appends an item to the head of a list.
# 0 :: x;; - : int list = [0; 1; 2; 3] # -1 :: 0 :: x;; - : int list = [-1; 0; 1; 2; 3]
while the @ operator concatenates two lists together.
# x @ [4;5];; - : int list = [1; 2; 3; 4; 5] # [4;5] @ x;; - : int list = [4; 5; 1; 2; 3]
Lists are typically broken apart using pattern-matching as in this polymorphic function:
> ocaml
# let rec len = function
[] -> 0
| head::tail -> 1 + len tail;;
val len : 'a list -> int = <fun>
# len x;;
- : int = 3
map f [x1;...;xn] = [f(x1);...;f(xn)]
> ocaml
# let rec map f list = match list with
[] -> []
| head::tail -> f head :: map f tail;;
val map : ('a -> 'b) -> 'a list -> 'b list = <fun>
# map (fun x -> x*x) [1;2;3;4];;
- : int list = [1; 4; 9; 16]
# map (fun x -> x ^ ".html") ["index";"hello";"foobar"];;
- : string list = ["index.html"; "hello.html"; "foobar.html"]
# let rec find p = function | [] -> raise Not_found | x :: l -> if p x then x else find p l;; # find (fun x -> x>0) [1;2;3];; - : int = 1 # find (fun x -> x<0) [1;2;3];; Exception: Not_found.
How could we use a higher-order function to sum a list of integers? Let's rewrite our infix + in prefix notation like we do for other functions, i.e. (+ 1 2) instead of 1 + 2.
1 + 2 + 3 + 4 + 5 1 + 2 + 3 + (+ 4 5) 1 + 2 + (+ 3 (+ 4 5)) 1 + (+ 2 (+ 3 (+ 4 5))) (+ 1 (+ 2 (+ 3 (+ 4 5))))
fold_right f a [x1;x2;x3] = f(x1 f(x2 f(x3 a)))
let rec fold_right f a = function | [] -> a | x :: xs -> f x (fold_right f a xs);; # fold_right (+) 0 [1;2;3;4;5];; - : int = 15 # fold_right ( * ) 1 [1;2;3;4;5];; - : int = 120
How many ways are there to make change in terms of half-dollars, quarters, dimes, nickels, and pennies?
The number of ways to make change for amount a is:
Degenerate cases: