intro_tut.ml

(**

* OCaml for the Curious 

  An Introductory tutorial in OCaml
  Compiled by Prasad Rao (raoprasadv AT gmail DOT com)
  Compiled together from various sources.

As this material is introductory
  _None_ of this material is likely to be original. I thank 
the sources from where I might have consciously and/or 
unconsciously.  

To tutorial authors:
Please treat this as a blanket apology if you feel like your
code has not been adequately acknowledge. Please send email
to raoprasadv at gmail dot com and I will correct the ommission


  This text is designed to be read using *org mode* for reading
  and tuareg mode while coding. 

This file is meant for line-by-line execution
preferably by using Ctrl-X Ctrl-e in Emacs Tuareg mode.
 -- not bulk loading
or compiling


PLEASE FEEL FREE TO COPY IT, FORWARD IT, USE IT etc. 


*)
(**

**   Acknowledgements

-  Real World Ocaml -- Jason Hickey, Anil Madhavapeddy, Yaron Minsky
- F# for Scientists -- Jon Harrop
- http://www.ffconsultancy.com/ocaml/bunny/
- http://strictlypositive.org/IdiomLite.pdf
- http://stackoverflow.com/questions/2030863/in-functional-programming-what-is-a-functor
- http://www.ocamlpro.com//files/ocaml-lang.pdf
- http://www.ocamlpro.com//files/ocaml-tools.pdf
- Practical O'Caml -- Joshua Smith
- http://www.cs.cornell.edu/courses/cs3110/2011sp/handouts/cheatsheet.pdf

And many, many other sources that I do not remember....

*)


(* 
** Functions
*** Defining a function                 :SHOW
*)
let inc x = x + 1;;

let sqr x = x * x;;
(** Note type inference *)

(* 
*** Calling a function 
When invoked with parameters a function
returns a value                            :SHOW
*)

inc 3;;

(* Note: Uses fewer parentheses *)


(*
*** Defining infix functions 
- See [[caml.inria.fr/pub/docs/manual-ocaml/expr.html][Rules for operators]]
 *)
let (|>) x f = f x;;
(* The type inferencer figures out that f is afunction *)


(* with this primitive you can chain computations 
naturally, assuming you read left to right! *)
1 |> inc |> inc |> inc;;

1 |> inc |> sqr ;;



let plus x y = x + y;;

(* 
*** partial application is clean
Compare it to Scala and Clojure 
 *)
let new_inc = plus 1;;

new_inc 1;;


(* 
*** functions as first class entities           :SHOW
*)
let compose f g x = f (g x);;


let inc2 = compose inc inc;;

inc2 0;;

let twice f = compose f f;;

let incinc = twice inc;;

incinc 3;;



(* 
*** Anonymous functions           :SHOW
- important to avoid polluting name space
with silly names like addone etc.                
*)

(fun x -> x + 1) 1;;

(*
** Arithmetic
*)

(* 
*** infix plus *)
1 + 1;;

(* 
*** use + as a  prefix   :SHOW
*)
(+) 1 1;;

(* 
*** But what is plus 
*)
(+);;

(* 
***  Multiplication 
*)
4 * 3;;


(* 
*** Floats use different operators +. *. /. etc.   :SHOW
*)
5. +. 4.;;

(* 
*** No automatic type casts             :SHOW
 Introduction to Error Messages
*)


(*ERR*)

5 + 4.;;

(* 
*** Explicit Typecasts 
Takes getting used to -- but I  began to like it 
*)
(float_of_int 5) +. 4.;;


(*
** Strings
*)
(* 
*** length
 *)
String.length "abc";;
(* What is String? *)
(* What is length *)

(* 
- Use repl to understand types
 *)
String.length;;


(* 
*** Lot less permissive than Java/Scala here 
*)
(*
ERR*)
"abc" + 4;;
(* *)
(*
*** String int concatenation
 Note:  Understanding error messages: You gave me String I need int 
*)

(* 
- Two ways of doing this 
*)
Printf.sprintf "%s%d" "abc" 4;;

"abc" ^ (string_of_int 4);;

(* 
*** String.concat
Equivalent of python join
 *)
String.concat "," ["a";"b";"c"];;

(*  
*** String.index
Remmeber OCamlbrowser
*)
String.index "abcdef" 'c';;

(* 9 
*** Str package 
has more goodies *)
#load "str.cma";;
Str.regexp;;


let r = Str.regexp_string "OCaml";;

let pos = Str.search_forward r "Lets find OCaml in the soup" 0;;

let my_chars = ['a';'b';'c'];;

(*
*** chars to string
*)
let implode l =
  let res = String.create (List.length l) in
  let rec imp i = function
  | [] -> res
  | c :: l -> res.[i] <- c; imp (i + 1) l in
  imp 0 l;;

implode my_chars;;

(*
*** string to chars 
 *)
let explode s =
  let rec exp i l =
    if i < 0 then l else exp (i - 1) (s.[i] :: l) in
  exp (String.length s - 1) [];;

explode "abc";;

(*
** Conditions
*)

5 < 6 ;;

5 <= 6;;

5  <= 2;;

5 != 2;;

(* ----------------------------- *)
(* you need to be more explicit*)
(* than in other languages*)
(* ------------------------------*)
(* ERR
5 < 2.0;;

5 <. 2.0;; (* Uh? *)
*)

5 < (int_of_float 2.0);;

(float_of_int 5) < 2.0;;
(* Why no <.? I dont know, but will find out *)

(*
** let for locals :SHOW
 *)

(* intoducing "locals" *)
let a = 1 and b = 2 in a < b;;

(*
** if 
*)

let a = 1 and b = 2 in if a < b then "Lesser" else "Greater";;

(*
**  you can specify types 
*)
let (a:int) = 1 and (b:int) = 2 in if a < b then "Lesser" else "Greater";;


(*
** Refs :SHOW
 *)


let p = ref [];;

p := 1::(!p);;

!p;;


(*
** Recursion  :SHOW

*** Factorial
 *)
let rec fact x =  (* use rec to explicitly signify recursion *)
  if x = 0 then 1
  else x * fact (x -1);;

fact 3;;
fact 10;;
fact 20;;
(*
*** Note! overflow
 *)
fact 25;;
fact 30;; (* Uh Oh! *)

(*
*** mutual recursion 
*)

let rec a x = 
  if x > 3 then b x
  else
    x -1
and   b x =   a (x -1);;

let foo = a 17;;

(*
*** tail call optimization demo :SHOW
*)

let identity x = x;;

let rec  no_tc_f n = 
  if n > 0 then
    let mu = no_tc_f (n - 1) in
    identity mu
  else
    1;;

let rec tc_f n =
  if n > 0 then 
    tc_f (n - 1)
  else
    1;;
(*
** See stack overflow
 *)
no_tc_f 375000;; 

(*
** tc optimization rulez!
 *)
tc_f  500000;;

(*
** Magic in Printf format conversion
*)
Printf.printf "%s" "sorry for not saying Hello World";;

Printf.printf  "sorry for not saying Hello World";;

(* What is Printf.printf *)
Printf.printf;;

"%s";;

(* Some magic afoot here -- for now just take it upon faith *)
Printf.printf "%s";;

(* TODO: Explain ('a, out_channel, unit) format -> 'a = <fun> clearly *)

(*
** Collections
 *)

(* range *)
(* recall the for loop *)
for x = 1 to 10 do Printf.printf "%d\n" x done;;

for;;
1 to 10;;
(* does not mean anything by itself *)

(* is -- defined? *)

(--);;


(* let us define our own *)

(* But first we need lists *)
[];;

(* TODO -- why does this not type  :: *)
(::);;

let moo_cons x y = x::y;;

3::[];;

2::3::[];;

'a'::3::[];;

(* Nyet *)
(2::3)::[];;





(* Now we are ready to define (--) *)
let rec (--) x y =
  if x > y then 
    []
  else
     x ::  ((x + 1) --  y);;

(* Yay  we defined our own range *)
(* TODO -- how do precedences work? *)

1 -- 10;;

(* Without pattern matching *)
let my_head_no_pm a_list =  List.nth a_list 0;;

my_head_no_pm [];;
(* not awesome *)

(* Cute, but Watch out *)
let my_head_0 (hd::_) = hd;;

(* works OK *)
my_head_0 [1;2;3];;
(* awesome *)

my_head_0 [];;
(* Not awesome *)

exception Tut_empty_list_not_allowed;;

try
  my_head_0 []
with Match_failure(_,_,_) -> raise Tut_empty_list_not_allowed;;



(* Cleaner than a meaningful exception is to 
   force all callers to do the right thing *)


(* None is Nulls propah cousin *)
let my_head a_list =
  match a_list with    (* This is pattern matching *)
      [] -> None
    | hd::_ -> Some hd;;

(* What should callers do? *)
let safe_print_head a_list =
  match my_head a_list with
      Some hd -> Printf.printf "%d" hd
    | None ->  Printf.printf "Cowardly refusal to print head of headless body";;

safe_print_head [];;
(* awesome *)

(* NOTE *)
(* f (f 1 (f 1 (f 1....(f 1 0))) *)

let my_sum = List.fold_left (+) 0;;

my_sum [1;1;1];;
(* awesome *)


min;;

(* NOTE *)
let my_min l = List.fold_left min (List.hd l) l;;

my_min [1;2;3];;

my_min [];;

my_min ["beta";"alpha";"gamma"];;


let color_names = [|"red";"white";"blue"|];;

Array.iter (Printf.printf "Should I buy a %s car?\n") color_names;;

(*
** Types and Pattern Matching
 *)

(*
*** Coordinates
 *)
type coordinate_int = int*int;;

let (+|) ((x1,x2): coordinate_int) ((y1,y2):coordinate_int):coordinate_int = (x1 +y1, x2 + y2);;

let a = 1,1;;

let (b:coordinate_int) = 2,2;;

a +| b;;

(*
*** Length
 *)


type length =
    Inch of float
  | Centimeter of float;;


let cent_of y =
  match y with 
      Inch x -> Centimeter (x *. 2.54)
    | Centimeter _ -> y;;

let inch_of y =
  match y with 
      Centimeter x -> Inch (x /. 2.54)
    | Inch _ -> y;;

let lengthFunc aFunc (x:length) (y:length) = 
  match x with
      Inch x_i -> Inch (aFunc x_i  ((fun (Inch z) -> z) (inch_of y)))
    | Centimeter x_i -> Centimeter (aFunc x_i ((fun (Centimeter z) -> z) (cent_of y)));;

let l_add = lengthFunc (+.) ;;

l_add (Inch 1.) (Centimeter 1.);;
l_add (Centimeter 1.) (Inch 1.);;

let l_sub  = lengthFunc (-.);;

(* Exercise -- Why Does this not work? *)
let l_gt = lengthFunc (>);;

(*
** Why use Functors

*** Defining a set of strings
*)


module StringSet = Set.Make(String);;

let foo = StringSet.add "abc" StringSet.empty;;
let foo_1 = StringSet.add "ABC" foo;;
StringSet.elements foo;;
StringSet.elements foo_1;;

(*
*** Creating a case insensive version with minimal work
*)
module CI_StringCmp = struct
  type t = string

  let compare (a:string)(b:string): int =
    let a_l = String.lowercase a in
    let b_l = String.lowercase b in
    if a_l < b_l then  -1
    else if a_l = b_l then  0
    else  1
end;;

module CI_String = Set.Make(CI_StringCmp);;

let ifoo = CI_String.add "abc" CI_String.empty;;

let ifoo_1 = CI_String.add "Abc" ifoo;;

CI_String.elements ifoo_1;;


(*
** Introducing functors
copied from http://stackoverflow.com/questions/2030863/in-functional-programming-what-is-a-functor
*)

(*
*** A module type: Order
*)
module type Order = sig
    type t
    val compare: t -> t -> bool
end;;

(*
*** module Integers
*)
module Integers = struct
    type t = int
    let compare x y = x > y
end;; 

(*
*** Write a reverse functor
*)

module ReverseOrder = functor (X: Order) -> struct
    type t = X.t
    let compare x y = X.compare y x
end;;


(* 
*** Invoking the ReverseOrder Functor
 *)
module K = ReverseOrder (Integers);;
Integers.compare 3 4;;   (* this is false *)
K.compare 3 4;;          (* this is true *)


module LexicographicOrder = functor (X: Order) -> 
  functor (Y: Order) -> struct
    type t = X.t * Y.t
    let compare (a,b) (c,d) = if X.compare a c then true
                         else if X.compare c a then false
                         else Y.compare b d
end;;


(* compare lexicographically *)
module X = LexicographicOrder (Integers) (Integers);;
X.compare (2,3) (4,5);;


module LinearSearch = functor (X: Order) -> struct
    type t = X.t array
    let find x k = 0 (* some boring code *)
end;;


module BinarySearch = functor (X: Order) -> struct
    type t = X.t array
    let find x k = 0 (* some boring code *)
end;;


(* linear search over arrays of integers *)
module LS = LinearSearch (Integers);;
LS.find [|1;2;3] 2;;
(* binary search over arrays of pairs of integers, 
   sorted lexicographically *)
module BS = BinarySearch (LexicographicOrder (Integers) (Integers));;
BS.find [|(2,3);(4,5)|] (2,3);;