[OCaml MOOC] week1: BASIC TYPES, DEFINITIONS AND FUNCTIONS

Sun, 23 Oct 2016 Category notes OCaml Series Part 2 of «Introduction to Functional Programming in OCaml»

1. BASIC DATA TYPES: int, bool

Rich type system and polymorphism in ocaml. Types are infered not declared.

Basic types: int, bool, float, string, char, ...

int

value: $-2^{62}$ ~ $2^{62}-1$ on 64-bit machines.
ops: +, -, *, /, mod (reminder: / is integer division)

# 3+2*4-1;; 
- : int = 10 
# 5/2;; 
- : int = 2 
# -5 mod 3;; 
- : int = -2

bool

values: true, false ops: &&,||, not comparison ops: <, >, =, <=, =>, <>
note 1: comparisons must have the same type of operands) note 2: equal test is = , = is NOT assigment. == exists but is for something else...

# true && (1<7);; 
- : bool = true 
# 1.0 < 7;; 
Error: This expression has type int but an expression was expected of type 
         float 
# 5 > "hello";; 
Error: This expression has type string but an expression was expected of type 
         int 
# 3=3;; 
- : bool = true 
# 3==3;; 
- : bool = true 
# 3<3.0;; 
Error: This expression has type float but an expression was expected of type 
         int 
# 3.0 < 3.0;; 
- : bool = false

2. MORE DATA TYPES: float, char, string

float

value: must written with a dot (5.0, 5.), or exponential (5e3, 6e-9) ops: also have a dot in the end +., -., *., /. functions: sqrt, sin, cos, ceil, floor, ...

# 3.0 +. 1e10;; 
- : float = 10000000003. 
# 2 + 3.0;; 
Error: This expression has type float but an expression was expected of type 
         int 
# 3. +. 2.0;; 
- : float = 5.

All basic types are disjoint: no value belongs to 2 different basic types, **no implicit conversion. **

conversion functions in both directions:

float_of_int: int -> float
int_of_float: float -> int

# float_of_int(2);; 
- : float = 2. 
# int_of_float(2.4);; 
- : int = 2 
# float_of_int 2;; 
- : float = 2. 
# int_of_float 2.8;; 
- : int = 2

Parentheses only necessary to indicate structure.

char

values: 256 chars (0~255), can be written as 'a' or '\087' conversion functions (char ↔ int):

Char.chr: int ->char
Char.code: char -> int

# Char.code 'A';; 
- : int = 65 
# Char.code '\122';; 
- : int = 122 
# Char.chr 233;; 
- : char = '\233' 
# Char.chr 65;; 
- : char = 'A' 
# Char.chr (Char.code 'B');; 
- : char = 'B'

string

values: written between "" ops: ^ for string concatenation functions: String.length, int_of_string, float_of_string, String.get(s,i) ...

# "abc" ^ "def";; 
- : string = "abcdef" 
# String.length "1234";; 
- : int = 4 
# int_of_string "123";; 
- : int = 123 
# int_of_string "123a";; 
Exception: Failure "int_of_string". 
# string_of_int 123;; 
- : string = "123" 
# String.get "abc" 1;; 
- : char = 'b'

3. EXPRESSIONS: if-then-else, func-applications and operators

expressions are used to compute values.

conditional expr

if... then... else... ⇒ this gives an expression, not an instruction.

An expression always have a type, type of the if-then-else expression is the type of the expressions in then and else, which must be the same.

If the else is missing → there is a default value, to be discussed later

# if 1<2 then 8 else 9;; 
- : int = 8 
# if 6=8 then 1 else 8;; 
- : int = 8 
# if 6=8 then 1 else 8.;;        
Error: This expression has type float but an expression was expected of type 
         int 
# if(if 1=1 then 2=2 else 3>2) then 2<3 else 3<2;; 
- : bool = true

function application

again, () are not needed unless indicate structure, and parentheses are NOT function applications...

# String.get;;  
- : string -> int -> char = <fun> 
# String.get "abcde" 2;; 
- : char = 'c' 
# String.get ("Hello"^"world") (3+2);; 
- : char = 'w' 
# String.get (string_of_int 65) (int_of_string "0");; 
- : char = '6' 
# String.get("hello", 2);; 
Error: This expression has type 'a * 'b 
       but an expression was expected of type string

Polymorphic operators

Some ops have polymorphic(generic) types, like >: 'a → 'a → bool Here the 'a is a type variable, can be instantiated by any type.

# 12 > 23.0;; 
Error: This expression has type float but an expression was expected of type 
         int 
# 'a' > 'b';; 
- : bool = false 
# "hello" > "world";; 
- : bool = false

4. DEFINITIONS

definitions are used to give names to values, in ocaml there are global defs and local defs.

global definition

effective for rest of session syntax: let name = expr once set, the value of the identifier never changes.

# let x = 2+3;; 
val x : int = 5 
# let y = 2*x;; 
val y : int = 10 
# let x = 3;; # **the old definition of x will be shadowed** 
val x : int = 3 
# x = x+1;; 
- : bool = false

local definition

naming within a delimited scope syntax: let name = expr1 in expr2 the scope of the identifier is expr2, the result's value is also expr2's value. So the identifier should appear in expr2.

# let x = 9 in 2*x;; 
- : int = 18 
# x;; # x is not in global scope  
Error: Unbound value x 
# let y = x+1 in y/3;; 
Error: Unbound value x 
# let x = 17;; # now x is global 
val x : int = 17 
# let y = x+1 in y/3;;           
- : int = 6

local defs can be nested:

# let x = 4 in  
  let y = x+1 in  
  let x = 2*y in x;; 
Error: Syntax error 
# let x = 4 in                    
  let y = x+1 in 
  let x=2*y in x;; 
- : int = 10 
# let x = 4 in  
  (let x=17 in x+1) + x;; 
- : int = 22

Simultaneous Definitions

can assign 2 identifiers in the same line:

    # let x1=2 and x2=3-3;; 
    val x1 : int = 2 
    val x2 : int = 0

Note: expr is evaluated w.r.t. the value bindings before the let.

# let x=2 in 
     let y=x+1 in (*y=2+1*) 
     x*y;; 
- : int = 6 
# let x=1;; 
val x : int = 1 
# let x=2 and y=x+1 in (*y=1+1 because the binding for x before the let is 1!*) 
    x*y;; 
- : int = 4

5. FUNCTIONS

func definition

global function (with 1 argument) def : let f x = expr

local def: let f x = expr1 in expr2

# let f x = x+1;; 
val f : int -> int = <fun> 
# f 17;; 
- : int = 18 
# let g y = 2*y 
  in g 42;; 
- : int = 84 
# f f 1;; (* interpreted as apply 2 argments to f, need parentheses here*) 
Error: This function has type int -> int 
       It is applied to too many arguments; maybe you forgot a `;'. 
# f (f 1);; 
- : int = 3

lexical scoping

def. lexical scoping identifiers(names) used in function body refers to the names *that *are visible at the moment of function definition.

def. dynamic scoping names refer to names that are visible at the moment of function invocation.

# let f x = x+1 in 
  let g y = f (f y) in (*here f is the f defined above, which is visible at the moment of g's declaration*) 
  let f x = 2*2 in (*this f is visible after g's declaration, it is visible when g is invocated*) 
  g 5;; (*g uses the first f*) 
Warning 26: unused variable f. 
- : int = 7 
(*the same is true for global scoping*) 
# let f x = x+1;; 
val f : int -> int = <fun> 
# let g y = f (f y);; 
val g : int -> int = <fun> 
# let f x = 2*x;; 
val f : int -> int = <fun> 
# g 5;; 
- : int = 7

identifiers are NOT variables

A name(identifier) can be hidden (the value is NOT changed) by a new definition of the same name.

The hidden identifier can be accessed with static(lexical) binding:

# let a = 1;; 
val a : int = 1 
# let f x = x+a;; 
val f : int -> int = <fun> 
# f 2 ;; 
- : int = 3 
# let a = 73;; 
val a : int = 73 
# f 2;; (*f still uses a's value as 2, the old value of a is NOT changed, it's hidden --closure? *) 
- : int = 3

6. RECURSION

rec functions are natural on recursively defined data structures.

example: fact(n)

recursive definition

using the f in let's expr will cause pb as f refers to the previous value of f. ⇒ use key word rec.

# let fact n = if n<=1 then 1 else n*fact(n-1);; 
Error: Unbound value fact 
# let rec fact n = if n<=1 then 1 else n*fact(n-1);; 
val fact : int -> int = <fun> 
# fact 10;; 
- : int = 3628800

mutually recursive function

ex. 2 funcs calling each other recursively

⇒ use simultaneous defs (let...and...):

# let rec even x = if x=0 then true else odd(x-1) 
  and odd x = if x=0 then false else even(x-1);; 
val even : int -> bool = <fun> 
val odd : int -> bool = <fun> 
# even 17;;  
- : bool = false 
# odd 10;; 
- : bool = false

exercices

let multiple_of n d =  
  (n mod d) == 0;; 

let integer_square_root n = 
  let sqr = sqrt (float_of_int n) in 
  int_of_float sqr; 

let rec gcd n m =  
  let big = max n m and small = min n m in  
  let r = big mod small in  
  if r=0 then small  
  else gcd r small;; 

let rec multiple_upto n r = 
  if r<2 then false  
  else if multiple_of n r then true 
  else multiple_upto n (r-1);; 

let is_prime n = 
  if n<=1 then false 
  else not (multiple_upto n (n-1));;