Appunti e Funzioni CAML Light

CAML light

Valore dell'espressione

Il nome che ho dato, determinato dopo aver fatto una valutazione del tipo...

# let n = 3+7;; n: int = 10

• Definizione Funzione

• # let f n = n+1;;

Nuova Funzione

• # let f (n,m) = n+m+3;;
• # f (3,5);;
• - : int = 8

Funzioni Curried (argomenti in sequenza)

# let f n m = n*m+3;;

La presenza del primo argomento (n) è necessaria per esprimere una funzione che prende un argomento m ed dà il risultato f.

Come trasformare una funzione nella versione curried

• # let t (n,m) = 2*n*m+m;;
• # let S n m = t (n,m);;
• S: int -> int -> int =

Funzioni polimorfe

• # let f x = x;;
• # f "abc";;
• - : string = "abc"
• # let f (n,m) = (n,m);;
• f : 'a*'b -> 'a*'b =

# let y (n,m) = (n, m+1);; # g(3, 4.5);; errore di tipo

Espressione Condizionale

if E₁ then E₂ else E₃

: bool, T=F, stesso tipo

# let rec f n = if n = Ø then Ø else 2+f(n-1);;

f : int -> int =

# f 3;; - : int = 6

f(3);; stack overflow

Liste

Sono strutture omogenee (elementi dello stesso tipo) con un ordine

Def: # [2,0, -,3,- 4];; - : int list = [ ... ]

[ ] lista vuota

# [5];; - : 'a b list = [5]

E’ definito in CAML un operatore di base costruttore di liste: :: (cons)

:: e’ un operatore infisso.

3::[2;3] = [3;2;3]

(3;4)::[ ] = [(3,4)]

# [3;4] :: [5];; errore di tipo

# let g n = n+1;; g : int -> int =

# f(g);; - : int -> int list =

Funzioni Predefinite

tl

muro dei nel elemento

# tl;; - : b list -> b list

head e hd; hd : a b list -> a fuono; hd default to partl(1)

# tl [true; false; true; true];; - : bool list = [false; true; true]

NB let n = n+1;; good

psi prede nel lupo

sul e suo gli disimogmenti

nello proguemazimulsia funzionare uss solo associazione nome valore

Cosa vogliamo dimostrare?

(∀n ∈ ℕ, ℓ ∈ ℕ list. take (n, ℓ) ⊕ chop (n, ℓ) = ℓ)

Caso base

1. take (0, ℓ) ⊕ chop (0, ℓ) = ℓ
2. take (0, []) ⊕ chop (0, []) = []

Casco induttivo

take (n, x::xs) ⊕ chop (n, x::xs) = x::xs ⇒ take (n+1, x::xs) ⊕ chop (n+1, x::xs) = x::x::xs

1) _{⊕ Del take 1^o patt. def chop 1^o patt.}

2) _{⊕ Del take 2^o patt. def chop 2^o patt.}

⊕ take (n+1, x::xs) ⊕ chop (n+1, x::xs) = x::xs

= ⊕ Del take 1^o patt. def chop 3^o patt.

Definiamo una funzione che dato per risultato il massimo di una lista non vuota

La funzione è corretta ma poco efficiente perché lo sviluppo di max è lista. Userò costrutto di dichiarazione locale

• inserisci alla lista l, un nuovo elemento con valore x immediatamente dopo il primo occorrenza del valore y.
• Se x non e' in lista, x non viene inserito.

# let rec inserisci l x y = not(null e with []) [[]]

1 2 :: 25 :: l z = y then if not(member y zs) then z :: x :: zs else z :: inserisci zs y else z :: inserisci zs x y;;

Quanto tempo in media impiega la funzione?

# let rec inserisci l x y =

reverse (prefixa (reverse l) x y)

Funzioni di ordine superiore - primo

hanno per argomento altre funzioni

# let somma x y = x + y;; somma : int -> int -> int = fun

# let apply f x =

apply : (0 -> 6, 5 -> 6 =

# let incr x = x + 1;; incr : int -> int =

apply incr 3;; => int = 4

# let somma (x, y) = x + y;; somma: int * int -> int =

apply somma (3, 4); apply : (int * int -> int) int * int -> int

Predicati: funzione di verita' su un booleano

# let prov x = x > 2;; prov : int -> bool =

# let somn (x, y) = x + y = 10;; somn : int * int = bool

Come controllo che un predicato valga su tutti gli elementi di una lista? Quantificazione universale

# let rec forall predicato lista = match lista with [] -> true x::xs when predicato x -> forall predicato xs x::xs male not predicato -> false;;

forall : (T -> bool) -> list -> bool = fun

Cancellare con una parola gli elementi che seguono l'ultimo occorrenza del valore 0. Se nessun elemento = 0, la lista è completamente cancellata.

Idea:

Boolean che mi dice se ho incontrato uno zero.

Let conc l = let f x (z,b) = f x (y,z,b) else

f x 0 then (x::l,b) else (l,false) e in let

Stesso esercizio, ma se la lista non contiene

Si definisco un lungo int List >= int e

let rec insim bt = match bt with

• Void -> []
• Node (x, lbt, rbt) -> ins lbt (x :: ins rbt)

let rec lina bt = match bt with

• Void -> 0
• Node (x, lbt, rbt) -> x :: (lame lbt @ lama rbt)

let max n m = if n > m then n else m;

let prof bt = match bt with

• Void -> 0
• Node (x, lbt, rbt) -> 1 + max (prof lbt) (prof rbt);;

let rec member el bt = match bt with

• Void -> false
• Node (x, lbt, rbt) when el -> true
• Node (x, lbt, rbt) when el < x -> member el lbt
• -> member el rbt;

let rec maxiv bt = match bt with

• Node (x, Void, rbt) when rbt Void -> let m = maxiv rbt in max x m;;
• Node (x, lbt, Void) when lbt Void -> let m = maxiv lbt in max x m;;
• Node (x, lbt, rbt) when lbt Void && rbt Void -> let m1 = maxiv lbt in max (max x m1) m2;;