Tutorial 2 CS2104

tut2.ml

(* Tutorial 2 : Recursion & Higher-Order Functions *)

(*
    OCaml Reading Resources

    tutorial:
        http://ocaml.org/learn/tutorials/

    introduction:
        http://www.cs.jhu.edu/~scott/pl/lectures/caml-intro.html

    real world ocaml book:
        https://realworldocaml.org/v1/en/html/index.html
*)


(*
  Q1: Load the naive fibonacci and a print method for a series of fibonacci.
    At which method call did the interpreter paused for some time?
    Fib(36) to Fib(40)
    *)

let rec fib n =
    if n<=1
        then 1
        else (fib (n - 1))+(fib (n - 2));;

let print_fib () =
    for i=1 to 40 do
        let _ = Printf.printf "Fib(%d) = %d \n" i (fib i) in flush(stdout)
    done;;

(*
  Q2: Load a more efficient version of fib2 below together with its
    print method. Take note of which call first has an integer overflow.
    *)

let fib2 n =
    let rec aux n =
        if n<=0 then (1,0)
                else let (a,b) = aux(n-1) in (a+b,a)
    in fst(aux n);;

let print_fib2 () =
    for i = 1 to 60 do
        let _ = Printf.printf "Fib(%d) = %d \n" i (fib2 i) in flush(stdout)
    done;;

#load "nums.cma"
open Num;;
open List;;
(*
  Q3: To avoid integer overflow, you can either use the big_int module or
    the following num module .

type num =
    |	Int of int
    |	Big_int of Big_int.big_int
    |	Ratio of Ratio.ratio

  http://caml.inria.fr/pub/docs/manual-ocaml/libref/Num.html

    Rewrite fib3 to use num type so that integer overflow does not occur.

    From top-level, first #load "nums.cma";; into memory.
    After that, open Num;;

You may need to use:
    num_of_int : int -> num
      string_of_num : num -> string
        +/ : num -> num -> num

    Run print_fib3 to get the first 100 fibs.

    *)

let fib3 (n:int) : Num.num =
    let zero = num_of_int 0 in
    let one = num_of_int 1 in
    let rec aux n =
        if n <=/ zero then (one,zero)
                  else let (a,b) = aux(n -/ one) in (a +/ b,a)
    in fst(aux(num_of_int n));;

let print_fib3 () =
    for i = 1 to 100 do
        let _ = Printf.printf "Fib(%d) = %s \n" i (Num.string_of_num(fib3 i)) in
        flush(stdout)
    done;;

(*
  Q4: You have been asked to implement a list of factorials.
    A naive way of implementing it is given below. The naive
    algorithm has O(n^2) complexity.

  Can you write a more efficient tupled recursive method to do this
        in O(n) time?

  To avoid integer overflow, change it to use the num type.
  *)

let rec fact n =
    if n==0 then 1
    else n * (fact (n-1));;

let rec factlist n =
    if n==0 then []
    else (fact n)::(factlist (n-1));;

let factlist (n:int) : Num.num list =
    let one = num_of_int 1 in
    let bn = num_of_int n in
    let rec aux (xs, m, s) =
        if s >/ bn then xs
        else aux ((m */ s) :: xs, m */ s, s +/ one)
    in aux ([], one, one);;
(*
  Q5: The following is a method to find the smallest
    value amongst a list of numbers. Re-implement it
    using (i) fold_right
          (ii) fold_left
          *)
(*
let rec fold_right f init xs =
    match xs with
      | [] -> init
      | y::ys -> f y (fold_right f init ys);;

let rec fold_left f init xs =
    match xs with
      | [] -> init
      | y::ys -> fold_left f (f y init) ys ;;
*)
let fold f z xs =
    let rec aux xs =
        match xs with
          | [] -> z
          | y::ys -> f y (aux ys)
    in aux xs;;

let id = fun x -> x

let fold' f z xs = fold_right f xs z;;
let fold'' f z xs = fold_left (fun g b x -> g (f b x)) id xs z;;

let rec fold'' f z xs =
    match xs with
      | []      -> z
      | (x::ys) -> fold_left f (fold'' f (f x z) ys) ys

let rec minlist xs =
    match xs with
      | [] -> max_int
      | y::ys -> min y (minlist ys);;

let minlist2 (xs: int list) : int = fold_right min xs max_int;;

let minlist3 (xs: int list) : int = fold_left min max_int xs;;

    (*
  Q6: In class, we mentioned that map and filter
    can be implemented in terms of fold.

    Show how this may be implemented.
    *)
let map2 (f:'a->'b) (xs:'a list) : 'b list =
    fold (fun x acc -> f x :: acc) [] xs;;

let filter2 (f:'a->bool) (xs:'a list) : 'a list =
    fold (fun x acc -> if f x then x :: acc else acc) [] xs;;

(*
  Q7: Given a list of strings, use filter
    and List.length to count strings that are smaller
    than a certain size. Write your code using the
    pipeline |> operator.

    *)
let ( |> ) (x:'a) (f:'a->'b) : 'b = f x;;

let count_str_smaller (n:int) (xs:string list) : int =
         map2 (String.length) xs
      |> filter2 ((>) n)
      |> List.length;;