Filter
Top Products
24 CHAPTER 3. FURTHER CAML
#let add m n f x = m f (n f x);;
add : (’a -> ’b -> ’c) -> (’a -> ’d -> ’b) -> ’a -> ’d -> ’c = <fun>
#let mul m n f x = m (n f) x;;
mul : (’a -> ’b -> ’c) -> (’d -> ’a) -> ’d -> ’b -> ’c = <fun>
#let exp m n f x = n m f x;;
exp : ’a -> (’a -> ’b -> ’c -> ’d) -> ’b -> ’c -> ’d = <fun>
#let test bop x y = defrock (bop (funpow x) (funpow y));;
test :
(((’a -> ’a) -> ’a -> ’a) ->
((’b -> ’b) -> ’b -> ’b) -> (int -> int) -> int -> ’c) ->
int -> int -> ’c = <fun>
#test add 2 10;;
it : int = 12
#test mul 2 10;;
it : int = 20
#test exp 2 10;;
it : int = 1024
The above is not a very efficient way of performing arithmetic operations. CAML
does not have a built-in function for exponentiation, but it is easy to define one by
recursion:
#let rec exp x n =
if n = 0 then 1
else x * exp x (n - 1);;
exp : int -> int -> int = <fun>
However this performs n multiplications to calculate x
n
. A more efficient way
is to exploit the facts that x
2n
= (x
n
)
2
and x
2n+1
= (x
n
)
2
x as follows:
#let square x = x * x;;
square : int -> int = <fun>
#let rec exp x n =
if n = 0 then 1
else if n mod 2 = 0 then square(exp x (n / 2))
else x * square(exp x (n / 2));;
exp : int -> int -> int = <fun>
#infix "exp";;
#2 exp 10;;
it : int = 1024
#2 exp 20;;
it : int = 1048576
Another classic operation on natural numbers is to find their greatest common
divisor (highest common factor) using Euclid’s algorithm:
#let rec gcd x y =
if y = 0 then x else gcd y (x mod y);;
gcd : int -> int -> int = <fun>
#gcd 100 52;;
it : int = 4
#gcd 7 159;;
it : int = 1
#gcd 24 60;;
it : int = 12