Functional Programming in OCaml: Prime, Fibonacci, and List Ops

This assignment presents a comprehensive exploration of functional programming in OCaml, covering key concepts and implementations. It begins with the implementation of prime number functions using recursion and discusses the use of tail recursion for optimization. The assignment then delves into the Fibonacci sequence, providing both recursive and tail-recursive implementations. It further explores the impact of static and dynamic scoping in the context of OCaml code. The assignment also provides solutions for list operations, including the `slice` function and the use of `fold_until` for efficient list manipulation. Finally, it demonstrates the use of `List.fold_left` for functions like `sum` and `concat`, emphasizing the importance of order in functional programming. The provided code snippets include examples of factorizing numbers using big integers and handling potential errors. The document showcases various functional programming techniques in OCaml, making it a valuable resource for students studying functional programming and AI.

FUNCTIONAL PROGRAMMING IN OCAML
Functional Programming in OCAML
Name
Institution
Date

FUNCTIONAL PROGRAMMING IN OCAML 2
1.
IMPLEMENTING THE PRIME NUMBER FUNCTIONAL PROGRAM
Printf.printf "Enter number: ";
let value = read_int () in
let is_prime x =
let bound = int_of_float (ceil (sqrt (float_of_int x))) in
let rec ip_aux x n =
if n > bound then true
else if (x mod n) == 0 then false
else (ip_aux x (n + 1))
in (ip_aux x 2)
in Printf.printf "%d is %s\n" value (if (is_prime value) then "prime" else "not prime")
OR
let is_prime n =
let n = abs n in
let rec is_not_divisor d =
d * d > n || (n mod d <> 0 && is_not_divisor (d+1)) in
n <> 1 && is_not_divisor 2;;
val is_prime : int -> bool = <fun>
# not(is_prime 1);;
- : bool = true

FUNCTIONAL PROGRAMMING IN OCAML 3
# is_prime 7;;
- : bool = true
# not (is_prime 12);;
- : bool = true
2.
IMPLEMENTING FIBONACCI SEQUENCE FUNCTIONAL PROGRAM
<pre>
# let rec fib n = if n<2 then n else fib(n-1) + fib(n-2);;
val fib : int -> int = <fun>
</pre>
For example:
<pre>
# fib 10;;
- : int = 55
</pre>
The function below can be built as tail recursive by collecting two subsequent
Fibonacci numbers.
<pre>
# let rec fib ?(r=1) ?(k=0) = function

FUNCTIONAL PROGRAMMING IN OCAML 4
| 0 -> k
| 1 -> r
| f -> fib ~r:(r+k) ~k:r (f-1);;
val fib : ?r:int -> ?k:int -> int -> int = <fun>
</pre>
3.
Given the program:
According to the OCaml program above using static or lexical scoping leads to the
following result:
A. Static Scoping
a) The outermost x is edged to 2.
b) The f is edge to x+y+z. Because x will be edged statically, it will amount to z (the
value of x is unchangeable because no variable can be assigned in OCAML
programming language.
c) The inner z will be edged to 4.
d) In the assessment of the function, destitute variables entailed in the code uses the
defined variable funy. A such, the environment x will edge to 2. Therefore, 2 + 4
= 6.

FUNCTIONAL PROGRAMMING IN OCAML 5
B. Dynamic Scoping
Evaluation of the code using dynamic scoping, it is assessed to 3 outcomes:
a) An outer x is edged to 2.
b) The z will be edged to funy is bound to funy→x+y+z. Hence it will occur that x
in code of z will not be constraint to an external assignment of z.
c) An inner y will be edged to 4.
d) During the assessment of the funy expression, destitute variables contained in
code of funy are measured through the environment of address, where z is 2.
Therefore, 2+4 makes it 6.
4.
FUNCTIONAL PROGRAMS IN OCAML

Providing two indicators, e and k, a slice program entails a list having elements
ranging from e to k elements from a master list. The elements are counted beginning from 0,
hence, the module numbers.
let slice list e k =
let rec take n = function
| [] -> []
| h :: t -> if n = 0 then [] else h :: take (n-1) t
in

FUNCTIONAL PROGRAMMING IN OCAML 6
let rec drop n = function
| [] -> []
| h :: t as l -> if n = 0 then l else drop (n-1) t
in
take (k - e + 1) (drop e list);;
val slice : 'a list -> int -> int -> 'a list = <fun>
However, a challenge posed by this answer is the take inability to be recursive,
thence, might end up running down the stack if the list provided is very long (Filliâtre et
al., 2018). It can be noticed from both structures of take and drop to be alike which may
prompt the developer to make a single frame in one sub-routine as shown below:
# let rec fold_until f acc n = function
| [] -> (acc, [])
| h :: t as l -> if n = 0 then (acc, l)
else fold_until f (f acc h) (n-1) t
let slice list i k =
let _, list = fold_until (fun _ _ -> []) [] i list in
let taken, _ = fold_until (fun acc h -> h :: acc) [] (k - i + 1) list in
List.rev taken;;
val fold_until : ('a -> 'b -> 'a) -> 'a -> int -> 'b list -> 'a * 'b list =
<fun>
val slice : 'a list -> int -> int -> 'a list = <fun>

FUNCTIONAL PROGRAMMING IN OCAML 7

#load "nums.cma";;
open Big_int;;
let cmd = [|"bigfact"; "8"; "9"; "96"; "2178";
"239322000000000000000000"; "25000000000000000000000000"; "17"|];;
(* This snippet code raises an exception of whether a nonnumeric string is in the
parametirised list
*)
let argList =
Array.map big_int_of_string (Array.sub cmd 1 ((Array.length cmd) - 1));;
let factorize num =
let two = big_int_of_int 2 and four = big_int_of_int 4 in
let rec genFactors (i,sqi) n fList =
if eq_big_int n unit_big_int then fList else
if lt_big_int n sqi then ((n,1)::fList) else
let newn = ref n and fcount = ref 0 in
while (eq_big_int (mod_big_int !newn i) zero_big_int) do
newn := div_big_int !newn i;

FUNCTIONAL PROGRAMMING IN OCAML 8
fcount := !fcount + 1;
done;
let nexti,nextsqi =
if eq_big_int i two then
(add_big_int i unit_big_int),
(add_big_int sqi (add_big_int (mult_big_int i two)
unit_big_int))
else
(add_big_int i two),
(add_big_int sqi (add_big_int (mult_big_int i four) two)) in
genFactors (nexti,nextsqi) !newn (if !fcount = 0 then fList else
((i,!fcount)::fList)) in
genFactors (two,four) num [];;

FUNCTIONAL PROGRAMMING IN OCAML 9
The formula prescribed is first passed into a devoid String for the first collector.
As such, a good resemblance amid the two formulas. The latter provides vantage to carry
off any kind of divergences amid both through authorizing the manipulator acting on the
direct list and accumulator (Gérard & Miller, 2018). A very powerful answer list formula
is as follows:
List.fold_left.
let rec fold_left (f : 'a -> 'b ->'a) (acc : 'a) (l : 'b list): 'a =
match l with

FUNCTIONAL PROGRAMMING IN OCAML 10
[] -> acc
| x :: xs -> fold_left f (f acc x) xs
Now we can rewrite sum and concat as
let sum (l : int list) : int =
List.fold_left (fun acc x -> acc + x) 0 l
let concat (l : string list) : string =
List.fold_left (fun acc x -> acc ^ x) "" l
Provided with function f of kind 'a -> 'b -> 'a, the formular List.fold_left f b [x1;
x2; ...; xn] asseses to f (... (f (f b x1) x2) ...) xn. 'left' in List.fold_left emanates from a
concept walking the list from left to right (Carbonneaux et al., 2017). Therefore, one must
be deliberate in the application of formulas in the correct order (thus acc ^ x and not x ^
acc in concat above).
5.

FUNCTIONAL PROGRAMMING IN OCAML 11

FUNCTIONAL PROGRAMMING IN OCAML 12
References
Carbonneaux, Q., Clément, F., & Weis, P. (2017). Sklml: Functional Parallel
Programming.
Filliâtre, J. C., Gondelman, L., Paskevich, A., Pereira, M., & de Sousa, S. M. (2018). A
Toolchain to Produce Correct-by-Construction OCaml Programs.
Gérard, U., & Miller, D. (2018). Functional programming with λ-tree syntax: Draft.